Könnte ein minimaler Schnitt einfacher sein als ein Netzwerkfluss?

18

Dank des Max-Flow-Min-Cut-Theorems wissen wir, dass wir jeden Algorithmus verwenden können, um einen maximalen Fluss in einem Netzwerkgraphen zu berechnen, um einen -Min-Cut zu berechnen . Daher ist die Komplexität der Berechnung eines minimalen ( s , t ) -Flusses nicht größer als die Komplexität der Berechnung eines maximalen ( s , t ) -Flusses.(s,t)(s,t)(s,t)

Könnte es weniger sein? Könnte es einen Algorithmus zur Berechnung eines Minimums geben, der schneller ist als jeder Max-Flow-Algorithmus?(s,t)

Ich habe versucht, eine Reduzierung zu finden, um das ) -Max-Flow-Problem auf das ( s , t ) -Min-Cut-Problem zu reduzieren, konnte aber keine finden. Mein erster Gedanke war, einen Divide-and-Conquer-Algorithmus zu verwenden: Finden Sie zuerst einen Min-Cut, der die Grafik in zwei Teile trennt; Finden Sie nun rekursiv einen Maximalfluss für den linken Teil und einen Maximalfluss für den rechten Teil und kombinieren Sie diese mit allen Kanten, die den Schnitt kreuzen. Dies würde in der Tat funktionieren, um einen maximalen Durchfluss zu erzeugen, aber seine Laufzeit im ungünstigsten Fall könnte bis zu dem O ( | V | ) -fachen der Laufzeit des Min-Cut-Algorithmus betragen. Gibt es eine bessere Reduzierung?(s,t(s,t)O(|V|)

Mir ist klar, dass der Satz von Max-Flow-Min-Cut zeigt, dass die Komplexität der Berechnung des Werts eines Max-Flow der Komplexität der Berechnung der Kapazität eines Min-Cut entspricht, aber das ist nicht das, wonach ich frage. Ich frage nach dem Problem, einen maximalen Durchfluss und einen minimalen Schnitt zu finden (explizit).

Dies hängt sehr eng mit der Berechnung eines maximalen Durchflusses aus einem minimalen Schnitt zusammen , außer: (1) Ich bin bereit, Cook-Reduzierungen (Turing-Reduzierungen) und nicht nur Karp-Reduzierungen (Viel-Eins-Reduzierungen) zuzulassen, und (2) Vielleicht können wir bei einen Graphen G 'finden, so dass der Min-Cut von G ' es einfach macht, den Max-Flow von G zu berechnen , was für diese andere Frage nicht möglich ist.GG′G′G

complexity-theory reductions network-flow graph-algorithms DW
quelle
2
@AshkanKzme, ich folge dir nicht; Kannst du das näher erläutern? Wie ich im 4. Absatz der Frage darlege, zeigt das Min-Cut-Theorem für den maximalen Durchfluss , dass der Wert des maximalen Durchflusses gleich der Kapazität des Min-Cut ist. Ich vermute, das ist es, woran Sie denken. Wenn Sie jedoch den Wert des Maximalflusses kennen, können Sie den Maximalfluss nicht selbst bestimmen (z. B. wie viel an jeder bestimmten Kante gesendet werden muss). Diese Frage fragt nach der Komplexität der Berechnung des Maximalflusses selbst und der Berechnung des Minimalschnittes selbst. Meine Frage ist genau wie im 2. Absatz der Frage angegeben.
DW
2
@AshkanKzme, Nein, ich habe keine falschen Annahmen gemacht. Sie gehen implizit davon aus, dass Ford-Fulkerson der schnellste Algorithmus ist, um einen Min-Cut zu finden ... aber meines Wissens hat das noch niemand bewiesen, und wir wissen nicht, ob das richtig ist oder nicht. Es klingt für mich so, als würden Sie den Standard-Rookie-Fehler mit untergeordneten Beweisen machen: "Ich sehe keinen Weg, um dieses Problem schneller zu lösen, also muss es unmöglich sein." (PS Du erzählst mir Standard-Lehrbücher über Max-Flow-Min-Cut. Ich schätze deinen Versuch zu helfen, aber ich bin bereits damit vertraut ...)
DW
1
In Bezug auf Ihre Aussage "Ich denke, es kann bewiesen werden, dass Sie, wenn Sie nur den Min-Cut haben, den maximalen Durchfluss erzielen können", empfehle ich Ihnen, eine Antwort mit dem Beweis dafür zu schreiben - denn das ist im Grunde genommen das, was Meine Frage ist gefragt. Ich habe noch nie einen Beweis dafür gesehen, aber wenn ja, hoffe ich, dass Sie ihn aufschreiben!
DW
1
@ DW Ich denke ich bekomme die Frage jetzt etwas besser. Ich glaube, es hat mich gestört, dass Sie die Polynomzahl reduziert haben. Würden Sie nicht eine konstante Spannungsreduktion benötigen, um beweisen, während selbst der Nachweis, dass keine solche Reduktion möglich ist, dies nicht widerlegt? f(n)=Θ(g(n))
Thomas Bosman
1
@ ThomasBosman, ja, das ist richtig. [Es tut mir Leid, dass ich dich verwirrt habe. Die Reduktion, die ich in der Frage gegeben habe, beweist, dass , was eine sehr schwache Untergrenze ist. Ich hoffe, dass es eine Reduktion gibt, die beweist, dass f ( n ) = Ω ( g ( n ) ) , aber ich weiß nicht, wie man so etwas konstruiert.]f(n)=Ω(g(n)/n)f(n)=Ω(g(n))
DW

Antworten:

-1

Hier ist ein möglicher Ansatz:

Angenommen, Sie kennen den Schnitt S, und dann ist das Auffinden des Flusses von nach t ein Minimalkosten- Netzwerkflussproblem mit null Kosten, da Sie den Abfluss an jedem Scheitelpunkt in V ∖ S und im Zufluss bei t genau kennen . Angenommen, f bezeichnet einen S - t - Fluss und A die Knotenbogenmatrix (dh Zeile i , Spalte j hat 1, wenn i der Schwanz von j ist , -1, wenn es der Kopf ist, sonst Null), und sei b so, dass A f = b wenn fStV∖StfS−tAijijbAf=bfbefriedigt das Angebot / die Nachfrage und die Flusserhaltung. Dann können wir mit der Gaußschen Eliminierung eine praktikable Lösung in Operationen.|V|3

Um einen Schnitt aus einem Fluss zu finden, müssen wir den Restgraphen konstruieren, der höchstens Zeit und dann möglicherweise überqueren | V | Ecken. |E||V|

Bei vollständigen Diagrammen und wenn der Minimalschnitt nur die Quelle oder nur die Senke ist, dauert die Reduzierung im ungünstigsten Fall in beiden Richtungen gleich lange. Ich denke jedoch, dass es schneller geht , eine praktikable Lösung für finden als | V | 3 angesichts der besonderen Struktur. Ich bin mir nicht sicher, wie ich das beweisen soll.Af=b|V|3

Thomas Bosman
quelle
f|V||E||E|>|V|
|V|bf
Af=b
Mist, das stimmt. Sie können die Einschränkungen (obere und untere) hinzufügen, von denen Sie wissen, dass sie eine Lösung haben, aber dann haben Sie | V | +2 | E | Reihen, so dass langsamer wäre, dann nur die maximale Strömung direkt zu berechnen.
Thomas Bosman
Das andere Problem ist, dass die Kapazitätsbeschränkungen Ungleichungen (nicht Gleichungen) sind, sodass Sie die Gaußsche Eliminierung nicht verwenden können: Sie müssten eine lineare Programmierung verwenden, die, wie Sie sagen, wahrscheinlich nicht schneller ist als nur die Berechnung der Maximaler Durchfluss direkt.
DW