Set saturi nel grafico bipartito

Question

Let $ g= (x \ cup y, e) $ essere un grafico bipartite non incontrato. Ci viene dato per ogni $ w \ subseteq x $ contiene quella $ | w | \ leq | n (w) | $ , dove $ n (w) $ è il vicinanza di $ W $ in $ y $ (condizione di matrimonio alias hall).

Il mio obiettivo è trovare un sottoinsieme $ W ^ * \ SOTETETQ x $ con $ | w ^ * |= | N (w ^ *) | $ , se esiste un sottoinsieme del tale sotto (ovviamente non è necessario esistere). Dal momento che non sono a conoscenza di un nome formale per questa proprietà, mi riferirei a una tale classica $ w ^ * $ come Set saturo .

Domande:

.
1. Questa proprietà è ampiamente nota? Ha un nome diverso?
2. Supponendo che la condizione del matrimonio detenga, è semplice dimostrare che anche ogni sindacato di serie saturi è saturata. Un problema interessante è trovare il set massimo saturo. Descrivo sotto una soluzione alquanto ingenua con runtime $ o (| v | \ clot | e |) $ , ma sospetto che possa essere risolto ancora più velocemente. Qualche idea?
3. Assumibilmente, un problema debolmente più facile è trovare un set saturo , non necessariamente il massimo (di nuovo, supponendo che la condizione di matrimonio detenga). Possiamo risolvere questo problema più velocemente di $ o (| v | \ clot | e |) $ ?

---

.

Modifica: Ecco uno schizzo per l'algoritmo che ho menzionato sopra: supponi che la condizione del matrimonio detenga per $ G $ . Quindi, come detto, con un lavoro di una teoria del bit possiamo mostrare che

Lemma: Let $ G $ Sii un grafico bipartite che soddisfa la condizione di matrimonio. Quindi, ogni sindacato di set saturi è anche saturato.

Il Lemma suggerisce che esiste un set massimo saturo unico. La domanda può quindi essere indicata in modo diverso:

.

Dato un nodo $ x \ in x $ , determinare se partecipa a un set saturo o non .

Se la risposta è sì, quindi partecipa anche al set massimo saturo. L'algoritmo pseudo va come segue:

.
1. Esegui il hopcroft-karp algoritmo per trovare una corrispondenza massima $ m $ che copre $ x $ in $ o ( \ sqrt {| v |} | e |) $ tempo. Una tale corrispondenza esiste a causa della condizione di matrimonio.
2. per ogni nodo $ x \ in x $ ,
   .
   • Aggiungi temporaneamente un nodo $ x '$ a $ x $ , che è collegato a ogni prossimo di $ x $ . Chiama il grafico ottenuto $ G_X $ .
   • Si noti che $ m $ è una corrispondenza parziale di $ g_x $ che è quasi massima (su a un bordo); Pertanto, possiamo trovare una maximatica corrispondenza $ M_X $ per $ G_X $ trovando un percorso di aumentazione in < Span Class="Math-Container"> $ G_X $ , in $ o (| v | + | e |) $ Tempo (stessi dettagli come in Hopcroft-karp).
   • se $ | m | <| m_x |, $ Continua. Altrimenti, se $ | m |= | m_x | $ , aggiungi $ x $ al set restituito.

L'analisi segue dai primi principi. Se esiste alcun set saturo $ w \ subseteq x $ con $ x \ in w $ , cioè $ | w |= | n_g (w) | $ allora $$ | W \ cup \ {x '\} |= | w | +1= | n_g (w) | + 1= | n_ {g_x} (w) | +1, $$ così $ w \ cup \ {x '\} $ viola la condizione di matrimonio in $ g_x $ . Di conseguenza, $ | m |= | m_x | $ . Possiamo mostrare analogamente che se $ x $ non partecipa a nessun set saturo, quindi $ | m_x |= | m | +1 $ .

Answer 1

Correggiamo una corrispondenza massima $ m $ . Let $ z \ SOCSETETQ Y $ Sii il set di nodi che non sono abbinati ai nodi in $ x $ . Possiamo vedere un nodo $ x \ in x $ appartiene a un set saturo se e solo se non esiste un percorso alternato da $ x $ a un nodo in $ z $ , cioè un percorso $ xy_1x_1 \ cdots y_kx_kz $ dove $ (x_i, y_i) \ in m $ e $ z \ in z $ (La dimostrazione è simile alla prova della correttezza del tuo algoritmo).

Così puoi aggiungere indicazioni per tutti i bordi in $ e $ tali che i bordi in $ m $ avere la direzione da $ x $ a $ y $ while bordi non in $ M $ Avere la direzione da $ y $ a $ x $ , Quindi i nodi in $ x $ che non sono raggiungibili da qualsiasi nodo in $ z $ make up the massimal Set saturo. È possibile eseguire un semplice BFS per vedere quali nodi in $ x $ è raggiungibile dai nodi in $ z $ . La complessità del tempo è $ o \ sinistra (\ sqrt {| v |} | e | \ destra) $ .