Conjuntos saturados em gráfico bipartido

Question

Deixe $ g= (x \ cup y, e) $ ser um gráfico bipartido indeciso. Recebemos que para cada $ w \ subseteq x $ é mantida que $ | w | \ leq | n (w) | $ , onde $ n (w) $ é o vizinho de $ W $ em $ y $ (condição de casamento de Aka Hall).

Meu objetivo é encontrar um subconjunto $ w ^ * \ subseteq x $ com $ | w ^ * |= | N (w ^ *) | $ , se tal subconjunto existir (obviamente, não é necessário existir). Desde que eu não estou ciente de um nome formal para esta propriedade, eu me referiria a tal $ w ^ * $ como um conjunto saturado .

Perguntas:

.
1. Esta propriedade é amplamente conhecida? Tem um nome diferente?
2. Assumindo que a condição de casamento detém, é simples mostrar que toda união de conjuntos saturados também está saturada. Um problema interessante é encontrar o conjunto saturado máximo. Eu descrevo abaixo uma solução um pouco ingênua com tempo de execução $ O (| v | \ Cdot | E |) $ , mas eu suspeito que possa ser resolvido ainda mais rápido. Qualquer ideia?
3. supostamente, um problema fraco é encontrar um conjunto saturado , não necessariamente o máximo (novamente, assumindo que a condição de casamento mantém). Podemos resolver este problema mais rápido do que $ O (| v | \ Cdot | E |) $ ?

---

edit: Aqui está um esboço para o algoritmo que mencionei acima: Suponha que a condição de casamento mantém para $ g $ . Então, como disse, com um trabalho de teoria de bits, podemos mostrar que

LEMMA: Deixe $ g $ ser um gráfico bipartido satisfazendo a condição de casamento. Então, toda união de conjuntos saturados também está saturada.

O Lema sugere que existe um conjunto saturado máximo único. A questão pode, portanto, ser declarada de forma diferente:

.

Dado um nó $ x \ em x $ , determine se ele participa de um conjunto saturado ou não .

Se a resposta for sim, também participa no conjunto máximo saturado. O algoritmo pseudo é o seguinte:

.
1. execute o hopcroft-karp algoritmo para encontrar uma correspondência máxima $ M $ que cobre $ x $ em $ o ( \ sqrt {| v |} | e |) $ tempo. Tal correspondência existe devido à condição de casamento.
2. para cada nó $ x \ em x $ ,
   • adicione temporariamente um nó $ x '$ para $ x $ , que está conectado a todos os vizinhos de $ x $ . Ligue para o gráfico que obtemos $ g_x $ .
   • Observe que $ m $ é uma correspondência parcial de $ g_x $ que é quase máximo (para cima para uma borda); Assim, podemos encontrar uma correspondência máxima $ m_x $ para $ g_x $ Encontrando um caminho de aumento span class="contêiner matemática"> $ g_x $ , em $ o (| v | + | e |) $ tempo (mesmos detalhes que em Hopcroft-Karp).
   • se $ | m | <| m_x |, $ Continue. Else, se $ | m |= | m_x | $ , add $ x $ para o conjunto de retorno.

A análise segue dos primeiros princípios. Se existe qualquer conjunto saturado $ w \ subseteq x $ com $ x \ in W $ , ou seja, $ | w |= | n_g (w) | $ então $$ | W \ cope \ {x '\} |= | w | +1= | n_g (w) | + 1= | n_ {g_x} (w) | +1, $$ Então $ w \ cope \ {x '\} $ viola a condição de casamento na $ g_x $ . Consequentemente, $ | m |= | m_x | $ . Podemos mostrar que, se $ x $ não participe de qualquer conjunto saturado, então $ | m_x |= | m | +1 $ .

Answer 1

Vamos fixar uma correspondência máxima $ m $ . Deixe $ z \ subseteq y $ Seja o conjunto de nós que não são correspondidos aos nós na $ x $ . Podemos ver um nó $ x \ em x $ pertence a um conjunto saturado se e somente se não houver um caminho alternado do contêiner de matemática $ x $ para um nó na $ z $ , isto é, um caminho $ xy_1x_1 \ cdoz y_kx_kz $ onde $ (x_i, y_i) \ in m $ e $ z \ in z $ (A prova é semelhante à prova de correção do seu algoritmo).

para que você possa adicionar direções a todas as bordas em $ e $ tais que bordas na $ m $ tem a direção de $ x $ para $ y $ enquanto as bordas não estão em $ m $ tem a direção de $ y $ para $ x $ , Em seguida, os nós em $ x $ que não estão acessíveis a partir de qualquer nó em $ z $ make up the Maximal conjunto saturado. Você pode executar um bfs simples para ver quais nós na $ x $ é acessível a partir de nós na $ z $ . A complexidade de tempo é $ o \ left (\ sqrt {| v |} | e | \ direita) $ .