Gesättigte Mengen im bipartiten Graphen

Question

Lassen $G=(X\cup Y, E)$ sei ein ungewichteter bipartiter Graph.Das bekommen wir für jeden $W\subseteq X$ das hält es $|W|\leq |N(W)|$, Wo $N(W)$ ist der Nachbarschaft von $W$ In $Y$ (auch bekannt als Halls Heiratsbedingung).

Mein Ziel ist es, eine Teilmenge zu finden $W^*\subseteq X$ mit $ | W^*| = | N (w^*) | $, wenn eine solche Teilmenge existiert (natürlich muss sie nicht existieren).Da mir kein offizieller Name für diese Immobilie bekannt ist, würde ich mich auf einen solchen beziehen $W^*$ Als ein gesättigter Satz.

Fragen:

1. Ist diese Eigenschaft weithin bekannt?Hat es einen anderen Namen?
2. Unter der Annahme, dass die Heiratsbedingung erfüllt ist, lässt sich leicht zeigen, dass jede Vereinigung gesättigter Mengen auch gesättigt ist.Ein interessantes Problem besteht darin, die maximal gesättigte Menge zu finden.Ich beschreibe im Folgenden eine etwas naive Lösung mit Laufzeit $O(|V|\cdot |E|)$, aber ich vermute, dass es noch schneller gelöst werden kann.Irgendeine Idee?
3. Angeblich ist ein wesentlich einfacheres Problem zu finden ein gesättigter Satz, nicht unbedingt das Maximum (wiederum unter der Annahme, dass die Heiratsbedingung erfüllt ist).Können wir dieses Problem schneller lösen? $O(|V|\cdot |E|)$?

---

Bearbeiten:Hier ist eine Skizze für den oben erwähnten Algorithmus:Gehen Sie davon aus, dass die Ehebedingung gilt $G$.Dann können wir das, wie gesagt, mit ein wenig theoretischer Arbeit zeigen

Lemma:Lassen $G$ ein zweiteiliger Graph sein, der die Heiratsbedingung erfüllt.Dann ist jede Vereinigung gesättigter Mengen auch gesättigt.

Das Lemma legt nahe, dass es eine eindeutige maximal gesättigte Menge gibt.Die Frage kann daher anders gestellt werden:

Gegeben ein Knoten $x\in X$, Bestimmen Sie, ob es an einer gesättigten Menge teilnimmt oder nicht.

Wenn die Antwort „Ja“ lautet, ist es auch Teil der maximal gesättigten Menge.Der Pseudoalgorithmus lautet wie folgt:

1. Führen Sie das aus Hopcroft–Karp Algorithmus, um eine maximale Übereinstimmung zu finden $M$ das deckt ab $X$ In $O(\sqrt {|V|}|E|)$ Zeit.Eine solche Übereinstimmung liegt aufgrund der Ehebedingung vor.
2. Für jeden Knoten $x\in X$,
   • Fügen Sie vorübergehend einen Knoten hinzu $x'$ Zu $X$, die mit jedem Nachbarn von verbunden ist $x$.Nennen Sie den Graphen, den wir erhalten $G_x$.
   • Beachte das $M$ ist eine teilweise Übereinstimmung von $G_x$ das ist fast maximal (bis zu einer Kante);Somit können wir eine maximale Übereinstimmung finden $M_x$ für $G_x$ indem wir einen ergänzenden Weg finden $G_x$, In $O(|V|+|E|)$ Zeit (gleiche Angaben wie in Hopcroft–Karp).
   • Wenn $|M|<|M_x|,$ weitermachen.Sonst, wenn $|M|=|M_x|$, hinzufügen $x$ zum zurückgegebenen Satz.

Die Analyse folgt ersten Prinzipien.Wenn eine gesättigte Menge vorhanden ist $W\subseteq X$ mit $x\in W$, d.h., $|W|=|N_G(W)|$ Dann$$ | w cup {x '} | = | w | +1 = | n_g (w) |+1 = | n_ {g_x} (w) | +1, $$Also $W\cup \{x'\}$ gegen die Ehebedingung verstößt $G_x$.Folglich, $|M|=|M_x|$.Wir können das analog zeigen, wenn $x$ nimmt also an keiner gesättigten Menge teil $|M_x|=|M|+1$.

Answer 1

Lassen Sie uns ein maximales Matching festlegen $M$.Lassen $Z\subseteq Y$ sei die Menge der Knoten, die nicht mit den Knoten in übereinstimmen $X$.Wir können einen Knoten sehen $x\in X$ gehört genau dann zu einer gesättigten Menge, wenn es keinen alternativen Pfad gibt $x$ zu einem Knoten in $Z$, also ein Pfad $xy_1x_1\cdots y_kx_kz$ Wo $(x_i,y_i)\in M$ Und $z\in Z$ (Der Beweis ähnelt dem Korrektheitsbeweis Ihres Algorithmus).

So können Sie allen Kanten Richtungen hinzufügen $E$ so, dass Kanten hineinkommen $M$ Habe die Richtung von $X$ Zu $Y$ während Kanten nicht in $M$ Habe die Richtung von $Y$ Zu $X$, dann die Knoten in $X$ die von keinem Knoten in erreichbar sind $Z$ bilden die maximal gesättigte Menge.Sie können ein einfaches BFS ausführen, um zu sehen, welche Knoten vorhanden sind $X$ ist von Knoten in aus erreichbar $Z$.Die Zeitkomplexität ist $O\left(\sqrt{|V|}|E| ight)$.