Berechnen Sie einen maximalen Durchfluss aus einem minimalen Schnitt

Wir wissen, dass die Berechnung eines maximalen Durchflusses resp. Ein Minimum-Cut eines Netzwerks mit Kapazitäten ist äquivalent. vgl. der Max-Flow-Min-Cut-Satz .

Wir haben (mehr oder weniger effiziente) Algorithmen zur Berechnung der maximalen Durchflussmengen, und die Berechnung einer minimalen Absenkung bei maximaler Durchflussmenge ist weder schwierig noch teuer.

Aber was ist mit dem Gegenteil? Wie können wir bei einem minimalen Schnitt einen maximalen Durchfluss bestimmen? Natürlich ohne Max-Flow von Grund auf zu lösen, und am liebsten auch schneller .

Einige Gedanken:

Aus dem Minimalschnitt kennen wir den maximalen Durchflusswert. Ich verstehe nicht, wie diese Informationen dem Standard helfen, den Pfad zu erweitern und neu zu kennzeichnen, obwohl die Anpassung des letzteren plausibler erscheint.
Wir können den Minimum Cut nicht verwenden, um das Netzwerk in zwei Teile aufzuteilen und wiederzuverwenden, da dies das Problem im schlimmsten Fall nicht verringert (wenn eine Partition ein Singleton ist). Auch hätten wir keinen Mindestschnitt der kleineren Instanzen.
Kennt man den Wert der maximalen Strömungsgeschwindigkeit, um die Max-Flow-LP zu lösen, möglicherweise über die komplementären Schlupfbedingungen?

algorithms graphs network-flow Raphael
quelle

Verwandte Frage: Kennen wir Algorithmen zur Berechnung von Min-Schnitten (die keine Max-Flow-Algorithmen verwenden)?

Raphael

Auf jeden Fall ist der randomisierte Algorithmus von Karger sehr beliebt, und Sie benötigen dafür keine Kenntnisse über die maximalen Flüsse.

Juho

Wenn Sie keine randomisierten Algorithmen wünschen, ist der Stoer-Wagner-Algorithmus sehr einfach, auch ohne Strömungstechniken.

Juho

Gutes Zeug! Hier gibt es eine weitere Herausforderung. Wenn Sie den Min-Cut kennen, wird nurInformationsbits (höchstens), da jeder Schnitt isomorph zu einer Teilmenge von . Ein maximaler Durchfluss kann jedoch viel mehr als benötigen zu darstellende Informationsbits (insbesondere, wenn die Kapazitäten groß sind). Informationstheoretisch kann man also nicht auf einen Algorithmus hoffen, der nur den Schnitt betrachtet und den Fluss ausspuckt. es müsste auch das Diagramm betrachten und einige zusätzliche Berechnungen durchführen. (Mir ist klar, dass dies keine große Barriere darstellt.)

| V |

$|V|$

V

$V$

| V |

$|V|$

Antworten:

Im schlimmsten Fall liefert der Minimalschnitt selbst nicht viele Informationen über den Maximalfluss. Man betrachte einen Graphen in dem das Minimum cut den Wert . Wenn ich durch Hinzufügen eines neuen Scheitelpunkts und einer Kante mit dem Gewicht , besteht ein Minimum von cut im neuen Diagramm nur aus der Kante aber das tut es nicht Geben Sie keine Informationen darüber, wie Sie Durchflusseinheiten von nach . $G=(V,E)$ $s,t$ $w$ $G$ $s'$ $(s',s)$ $w$ $s',t$ $(s', s)$ $w$ $s$ $t$

Tatsächlich gibt der Minimalschnitt Auskunft über den Wert des Durchflusses, nicht jedoch darüber, wie dieser Durchfluss erzielt werden kann. Dies bedeutet, dass das Erkennen des minimalen Schnitts das Finden des Flusses um höchstens einen logarithmischen Faktor beschleunigen kann, da wir eine binäre Suche durchführen könnten, um den Wert des Schnitts zu finden.

Tom van der Zanden
quelle

Dieser logarithmische Faktor hängt jedoch von der Größe des Intervalls der potenziellen Durchflusswerte ab und ist daher nicht mit den bestehenden Obergrenzen für die Lösung des maximalen Durchflusses zu vergleichen, die nur von der Diagrammgröße abhängen. Trotzdem wäre auch eine logarithmische Beschleunigung von Interesse. Ich bin nicht davon überzeugt, dass es überhaupt nicht hilft, den Wert eines max-flow zu kennen.

Raphael

-2

Es gibt sicherlich Algorithmen, mit denen Sie den minimalen Schnitt berechnen können, bevor Sie den maximalen Fluss berechnen. Zwei solche Algorithmen sind die Push-Relabel- und die Pseudoflow-Algorithmen, die eng miteinander verwandt sind. Letzteres ist effizienter. Beide Algorithmen verwenden spezielle Eigenschaften des Residuendiagramms, das sie iterativ verbessern, um den Maximalfluss aus dem Minimalschnitt abzuleiten. Für Details empfehle ich dringend, den Code und die Artikel zu lesen.

Um den Fall des Push-Relabels zu erläutern, wird garantiert, dass der Algorithmus einen minimalen Schnitt berechnet hat, wenn er keinen Fluss mehr zur Spüle drückt. Dieser Teil des Algorithmus wird mangels eines besseren Namens als Phase 1 bezeichnet. Phase 2 ist die effizientere Phase, in der der Min-Cut in einen Max-Flow umgewandelt wird, indem Zyklen im Restgraphen iterativ mit einer einzelnen Tiefensuche abgebrochen und überschüssiges Material zur Quelle zurückgeschoben wird. Ich glaube, dass Phase 2 nachweislich asymptomatisch effizienter ist als Phase 1.

ldog
quelle

Bitte lesen Sie die Frage erneut. es ist nicht die, die du beantwortet hast.

Raphael

Das Beispiel für PR, das ich gegeben habe, geht davon aus, dass Sie während der Berechnung von Min-Cut andere Informationen berechnet haben. In Ihrer ursprünglichen Frage wurde nicht angegeben, ob Sie andere Informationen zusammen mit dem Min-Cut pflegen dürfen, um die nachfolgende Maxflow-Berechnung zu vereinfachen. Ist es angemessen, Ihre ursprüngliche Frage wie folgt zu formulieren: " Wie können wir einen maximalen Durchfluss bestimmen, wenn wir einen Mindestschnitt und keine weiteren Informationen erhalten ?".

ldog

Ich stellte fest, "A gegeben, B berechnen". Die einzig vernünftige Annahme ist, dass Sie nur A erhalten, sonst wäre es eine sehr verschwommene Angelegenheit, über Rechenprobleme zu sprechen.

Raphael

Ich bin anderer Ansicht. Aus praktischer Sicht würden Sie niemals einen Min-Cut berechnen, ohne zusätzliche Informationen (wie die im PR-Algorithmus) zu berechnen. Aus theoretischer Sicht ist es möglicherweise hilfreich, die Dinge isoliert zu betrachten, wie Sie sagen. Der Kontext ist hier der Schlüssel.

ldog