Maximaler unabhängiger Satz eines zweigeteilten Graphen

19

Ich versuche den Maximum Independent Set eines Biparite Graph zu finden.

In einigen Notizen "13. Mai 1998 - University of Washington - CSE 521 - Anwendungen des Netzwerkflusses" fand ich Folgendes :

Problem:

Bei einem zweiteiligen Graphen , findet einen unabhängigen Satz , die so groß wie möglich ist, wobei und . Eine Menge ist unabhängig, wenn keine Kanten von zwischen Elementen der Menge vorhanden sind.G=(U,V,E)UVUUVVE

Lösung:

Konstruieren Sie ein Flussdiagramm auf den Eckpunkten . Für jede Kante gibt es eine unendliche Kapazitätskante von nach . Für jedes gibt es eine Einheitskapazitätskante von bis , und für jedes gibt es eine Einheitskapazitätskante von bis .UV{s,t}(u,v)EuvuUsuvVvt

Finden sie eine endliche Kapazität Schnitt , mit und . Lassen und . Die Menge ist unabhängig, da keine Kanten mit unbegrenzter Kapazität den Schnitt kreuzen. Die Größe des Schnitts ist. Um die unabhängige Menge so groß wie möglich zu machen, machen wir den Schnitt so klein wie möglich.(S,T)sStTU=USV=VTUV|UU|+|VV|=|U|+|V||UV|

Nehmen wir das als Diagramm:

A - B - C
    |
D - E - F

Wir können dies wie folgt in einen zweigeteilten Graphen aufteilen (U,V)=({A,C,E},{B,D,F})

Wir können durch Brute-Force-Suche feststellen, dass die einzige maximale unabhängige Menge . Versuchen wir die obige Lösung durchzuarbeiten:A,C,D,F

Die konstruierte Flussnetz-Adjazenzmatrix wäre also:

stABCDEFs00101010t00010101A1000000B01000C1000000D0100000E10000F0100000

Hier stecke ich fest, der kleinste begrenzte Kapazitätsabbau, den ich sehe, ist trivial: mit einer Kapazität von 3.(S,T)=({s},{t,A,B,C,D,E,F})

Die Verwendung dieses Schnitts führt zu einer falschen Lösung von:

U=US={}
V=VT={B,D,F}
UV={B,D,F}

Während wir erwartet haben ? Kann irgendjemand erkennen, wo ich in meinem Denken / Arbeiten einen Fehler gemacht habe?UV={A,C,D,F}

Andrew Tomazos
quelle
(S, T) = ({s, A, B, C}, {t, D, E, F}) hat Kapazität 2
1
@Brian es gibt eine unendliche Kapazitätsgrenze von B nach E in Ihrem Schnitt, also eine unendliche Kapazität.
Andrew Tomazos
Wenn ich das richtig verstehe, basierend auf der Brute-Force-Lösung, brauchst du einen Schnitt, bei dem S A und C enthält und T D und F enthält, was deinen Schnitt zu {s, A, C}, {t, D, F} macht. . Nun, wie konstruierst du den Schnitt?
njzk2
auch sieht dies aus wie der Ford-Fulkerson, bei dem Kanten eine Kapazität von eins haben.
njzk2
Schlagen Sie den ungarischen Algorithmus nach.
Patrik Vörös

Antworten:

14

Das Komplement einer maximalen unabhängigen Menge ist eine minimale Scheitelabdeckung.

Um eine minimale Scheitelpunktabdeckung in einem zweigeteilten Graphen zu finden, siehe König's Theorem .

Jukka Suomela
quelle
2
Dies löst (vielleicht) das Problem, beantwortet aber nicht die Frage.
Raphael
2
@Raphael: Ich stimme zu, wenn Sie das Wort "vielleicht" entfernen. :)
Jukka Suomela
1
Oh, ich bin sicher, dass es das Problem löst , aber ich bin nicht sicher, ob es Andrew hilft , sein Problem zu lösen.
Raphael
3
Ich habe es gelöst, wie Sie vorgeschlagen haben: HopcroftKarp -> maximale Übereinstimmung -> Konigs Thereom -> Minimale Vertex-Abdeckung -> Komplement -> Maximale unabhängige Menge. Ich möchte immer noch wissen, warum die in meiner Frage beschriebene Strömungsmethode nicht funktioniert.
Andrew Tomazos
5

Die angegebene Lösung ist eindeutig falsch, wie Sie anhand des Gegenbeispiels demonstrieren. Beachten Sie, dass der Graph U + V eine zusammenhängende Komponente durch die Kanten mit unendlicher Kapazität ist. Daher muss jeder gültige Schnitt alle A, B, C, D, E, F auf derselben Seite enthalten.

Beim Versuch zurückzuverfolgen, woher die Lösung stammt: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf nennt Network Flows von Ahuja, Magnanti und Orlin für einige der Probleme. Dieses Buch ist nicht urheberrechtlich geschützt und kann von http://archive.org/details/networkflows00ahuj heruntergeladen werden , enthält jedoch anscheinend nicht dieses Problem und diese Lösung (es wird nach jedem Auftreten von "zweigeteilt" gesucht).

Beachten Sie, dass der Erklärungsabschnitt der Lösung nicht zeigt, dass der kleinste Ausschnitt des von ihm erstellten Diagramms der maximalen unabhängigen Menge entspricht. Es zeigt nur einen Weg, einen unabhängigen Satz zu erhalten.

Und doch können Sie sehen, was der Algorithmus versucht zu tun. Hier ist, was die tatsächliche maximale unabhängige Menge in Bezug auf ihren s, t-Schnitt entspricht:

Graph

Die Kante mit unendlicher Kapazität, die den Algorithmus unterbricht, wird hervorgehoben.

Ich bin mir nicht sicher, wie ich den Algorithmus auf das bringen soll, was beabsichtigt war. Vielleicht sollten die Kosten einer unendlichen Flanke Null sein, wenn sie rückwärts geht (dh wo sie von S nach T geht, aber von t nach s überquert)? Aber ist es bei dieser Nichtlinearität immer noch leicht, den minimalen / maximalen Durchfluss zu finden? Wenn wir über eine Möglichkeit nachdenken, die Lösung von @Jukka Suomela für den Algorithmus von der Frage abzukoppeln, gibt es eine Schwierigkeit, wenn wir von der maximalen Anpassung zur minimalen Vertex-Abdeckung übergehen: Die maximale Anpassung kann durch einen max-flow ermittelt werden Wie können Sie die minimale Scheitelpunktabdeckung mithilfe eines flussähnlichen Algorithmus wiederherstellen? Wie hier beschriebenNachdem die maximale Übereinstimmung gefunden wurde, werden die Kanten zwischen U und V gerichtet, um die minimale Scheitelpunktabdeckung zu finden. Dies zeigt also wiederum nicht, dass eine einfache Anwendung von Min-Cut / Max-Flow alles ist, was zur Lösung dieses Problems erforderlich ist.

Evgeni Sergeev
quelle
2

STS

yu25x
quelle
1
Ich stimme Ihnen zu, aber können Sie bitte weitere Details hinzufügen, z. B. einen vollständigen Korrektheitsnachweis des Flussalgorithmus und die Anwendung des Algorithmus auf das OP-Beispiel?
Xskxzr
Der Hinweis in diesem Dokument enthält einen kurzen Beweis für die Richtigkeit. cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf Wenn Sie sich zum Beispiel die Abbildung von Evgeni Sergeev oben ansehen, sollten die Kanten alle nach unten gerichtet sein. Dann sind die einzigen zwei Kanten von S (s, e) und (b, t), die fettgedruckte rote Kante geht nach S und sollte nicht im Schnittwert gezählt werden.
15.
0

Der Schnitt sollte auf dem tatsächlichen Durchfluss liegen, nicht auf den Kapazitäten. Da der Fluss von s endlich ist, ist jeder {S, T} -Schnitt endlich. Der Rest ist wie oben erklärt.

Talmon
quelle
1
Bist du sicher? Schnitte sind in der Regel kapazitiv, und wir wissen bereits, dass der minimale Schnitt endlich ist, sodass unendliche Schnitte nicht das Problem zu sein scheinen.
David Richerby
0

UV

G{A,C,D,F}

Ajit Kumar
quelle