Super Mario fließt in NP?

Eine klassische Erweiterung des Max-Flow-Problems ist das "Max-Flow-over-Time" -Problem: Sie erhalten einen Digraphen, von dem zwei Knoten als Quelle und Senke unterschieden werden, wobei jeder Bogen zwei Parameter hat, eine Kapazität pro -Einheitszeit und eine Verzögerung. Sie sind auch einen Zeithorizont gegeben . Das Ziel ist es, einen zeitlichen Fluss zu berechnen, der die maximale Materialmenge von der Quelle zur Senke bis zur Zeit . Ein Fluss mit maximalem Wert kann in Polynomzeit durch eine geschickte klassische Reduktion auf minimale Kosten und maximalen Fluss berechnet werden. $T$ $T$

Ich bin an einer Erweiterung dieses Modells interessiert, bei der Kanten einen dritten "Lebensdauer" -Parameter haben. Wenn ein Lichtbogen Lebensdauer hat , und ist der früheste Zeitpunkt , an dem eine positive Strömung wird durch den Bogen geschickt, dann zerstören wir den Bogen zum Zeitpunkt . Sie können sich das wie die Plattformen in Super Mario Brothers vorstellen, die wegfallen / zerstört werden, sobald Sie darauf treten, oder Sie können sich diese als Batterien vorstellen, die für die Stromversorgung der Ränder benötigt werden und nach dem Einschalten nicht mehr ausgeschaltet werden können . ( Editieren :) Das Entscheidungsproblem ist, wenn auch eine Flusswertuntergrenze , ob ein Fluss eingeplant werden kann, der sowohl die Zeithorizontobergrenze als auch die Flusswertuntergrenze erfüllt. $\ell$ $t$ $t+\ell$ $B$

Bisher kann ich feststellen, dass dieses Problem stark NP-hart ist (über 3-Partitionen). Aber ich weiß eigentlich nicht, ob es sich um NP handelt: Gibt es eine Garantie dafür, dass eine Lösung kompakt ausgedrückt werden kann? In der klassischen Version wird eine spezielle Art der optimalen Strömung verwendet, um dieses Problem zu umgehen.

Hinweis: Das obige Modell ist etwas zu wenig spezifiziert, da Sie möglicherweise die Bevorratung von Datenströmen an Knoten zulassen oder nicht zulassen und möglicherweise ein diskretes oder ein kontinuierliches Zeitmodell verwenden. Die Lösung der Frage für eines dieser Modelle wäre ausgezeichnet.

ds.algorithms graph-algorithms network-modeling max-flow-min-cut daveagp
quelle

Ich bin mir nicht sicher ob ich das verstehe. Warum gibt es ein Problem beim kompakten Ausdrücken eines bestimmten Flussplans und beim Überprüfen, ob der Gesamtfluss in Polyzeit mindestens F beträgt?

Suresh Venkat

Sie überlegen sich vielleicht, wie Sie beweisen können, dass die Ausgabe eines Optimierungsproblems, dessen Ausgabe ein zeitgesteuerter Ablauf ist, in Polyzeit auf Optimalität überprüft werden kann. Oft zeigt sich jedoch, dass Entscheidungsprobleme mit nur Ja / Nein-Antworten in NP vorliegen, und Optimierungsprobleme, die eine Funktion wie den Fluss maximieren, werden typischerweise in ein Entscheidungsproblem umgewandelt, indem der Eingabe ein unterer Grenzwert B hinzugefügt wird, und das Entscheidungsproblem wird "Gibt es eine Lösung mit einem Wert von mindestens B?"

andy_fingerhut

Suresh: Sagen wir im diskreten Modell, die natürliche Art, einen Flussplan auszudrücken, benötigt

ganze Zahlen für jeden Bogen, aber dies ist kein Polynom, sondern nur ein Pseudo-Polynom in der Eingabegröße. Ähnlich sehe ich im kontinuierlichen Modell nicht, wie man das komprimiert.

T

$T$

Daveagp

Andy: Sie haben recht, formal ist es für mich besser, dies als Entscheidungsproblem zu bezeichnen, indem ich zusätzlich zu einem Zeithorizont eine Untergrenze für den Wert habe. Dann ist es etwas, für das wir fragen könnten, ob es in NP liegt.

Daveagp

@daveagp: Hast du PSPACE-Härte ausprobiert, zum Beispiel QBF auf dein Problem reduziert?

Yoshio Okamoto

Antworten:

Es ist lange her, aber ich bin mir ziemlich sicher, dass dieses Problem in P. ist.

Ich schrieb 1995 meine Doktorarbeit darüber. Siehe "Efficient Dynamic Network Flow Algorithms" von Bruce Hoppe, eingereicht bei Cornell CS. Online unter http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

Siehe Kapitel 8, "Erweiterungen", Abschnitt 8.1 über "sterbliche Kanten".

Bruce Hoppe
quelle

"Es war eine dunkle und stürmische Nacht. Jack lag bewegungslos in seiner Kabine - bewegungslos mit Ausnahme seines Magens, der sich wie ein verrückter Karnevalsritt in seinem Bauch drehte ..." (Seite xiii, wo der Autor praktische Anwendungen bespricht).

Neal Young

Nettes Zitat, Neal! :) Übrigens macht daveagp einen guten Punkt, wenn es darum geht, Pseudo-Polynom-Raum zu benötigen, um den "Fluss" zu speichern, der die Entscheidungsfrage beantwortet. Wie man nicht nur den optimalen Fluss findet, sondern auch darstellt, dass der Fluss in P den Kapiteln 1-7 meiner Dissertation entspricht

Bruce Hoppe,

Ausgezeichnet! Ich habe das alles endlich gelesen. Sobald wir das erste Mal festgestellt haben, dass der Datenfluss eine Kante erreicht, ist die Machbarkeit des Netzwerks mit den daraus resultierenden Start- und Endzeiten in P (unter der Annahme, dass ein Holdover zulässig ist), und daher liegt das ursprüngliche Problem in NP: In unserem polynomgroßen Zertifikat ist die Startzeit für aufgeführt jede Kante. Super Mario fließt daher NP-vollständig. Zufällige Fragen: Ändert das Verbieten eines Holdovers etwas? Gibt es einen anständigen Approximationsalgorithmus?

Daveagp

BEARBEITEN: Die Antwort ist FALSCH. Ich habe die (alberne) implizite Annahme getroffen, dass ein Pfadfluss, der zum Zeitpunkt s beginnt und zum Zeitpunkt t endet und die Kante e durchläuft, die Kante e für diese Dauer blockiert. Dies ist jedoch nicht wahr. Sehen *.

Hinweis: Möglicherweise ist dieser Ansatz unnötig kompliziert oder falsch. Obwohl ich versucht habe, es zu überprüfen und sorgfältig aufzuschreiben, habe ich nicht viel Zeit darauf verwendet.

Unter der Annahme, dass eine Bevorratung nicht zulässig ist, muss der Durchfluss sofort übertragen werden. Es sei die Anzahl der Kanten und die Eingangslänge. Ich habe keine kontinuierliche oder diskrete Zeit angegeben, da ich dies nicht berücksichtigt habe. Es sollte für diskretes Denken funktionieren, für kontinuierliches Ich bin mir sicher. $m$ $N$

Dann können wir die Lösung als eine Menge von "Pfadflüssen" von der Quelle zur Senke beschreiben. Ein Pfadfluss ist ein Vierfacher der aus Folgendem besteht: Ein einfacher Pfad von der Quelle zur Senke; Startzeit des Pfadflusses ; Durchflussmenge durch den Weg ; Durchsatzrate . $(P,s,a,r)$ $P$ $s$ $a$ $r$

Es sei eine Lösung durch eine Menge von Pfadflüssen gegeben. Wir können überprüfen, ob die durch diese Pfadflüsse gegebene Lösung im Zeitpolynom in korrekt ist und : $F$ $|F|$ $N$

Addieren Sie für jede Flanke und einen Zeitpunkt die Durchsatzrate aller über gehenden zum Zeitpunkt . Jeder Pfadfluss hat eine Start- und eine Endzeit, daher müssen wir nur die Zeitpunkte berücksichtigen, zu denen ein Pfadfluss beginnt oder endet (zwischen diesen Zeitpunkten ändert sich nichts in Bezug auf die Pfadflüsse, die über die Kante . $e$ $t$ $e$ $t$ $e$
Für jeden Pfadfluss können wir überprüfen, ob der gesamte Fluss vor der Zeit an der Senke ankommt . $T$
Für jede Kante können wir überprüfen, ob ein Pfadfluss durchläuft, nachdem er zerstört wurde oder nicht.
Die untere Grenze des Flusses wir einfach überprüfen, indem wir die Mengen des Flusses der Flusspfade addieren. $B$

Nun müssen wir 'nur' zeigen, dass die Anzahl der Pfadflüsse in polynomial ist . $N$

Für eine gegebene Lösung können wir die Zeit bestimmen, zu der ein Fluss eine Kante passierte und wann die Kante zerstört wurde. Wandeln Sie dies in ein Problem mit einer äquivalenten Lösung um: Es gibt feste Grenzen an jeder Kante, wann sie verwendet werden kann und wann nicht - eine Start- und eine Endzeit. Lassen Sie bezeichnen die Menge all dieser Zeiten. $\{t_1,...,t_k\}$

Betrachten Sie eine nicht kompakte Lösung und (anfangs) eine leere Menge von Pfadflüssen. Die Idee ist, dass wir iterativ einen Pfadfluss in der nicht kompakten Lösung finden, ihn entfernen und in unserem Satz von Pfadflüssen speichern.

Finden Sie Pfadflüsse, die zwischen und beginnen und enden , aber nicht zwischen und enden, so dass . Lassen bezeichnet den Satz von Pfadflüsse zwischen und mit den Eigenschaften , wie oben beschrieben. $t_i$ $t_j$ $i<j$ $t_p$ $t_q$ $[t_p,t_q] \subseteq [t_i,t_j]$ $F_{i,j}$ $t_j$ $t_j$

Angenommen, wir haben bereits alle Pfadflüsse für alle kleineren Intervalle als . Finden Sie gierig Pfadflüsse, die in beginnen und enden . Wenn wir einen finden, entfernen Sie diesen Fluss aus der Lösung und passen Sie die Durchsatzraten der Eckpunkte und die Menge des Flusses, der von der Quelle zur Senke gesendet wird, entsprechend an. Für diesen Pfadfluss maximieren wir den Durchsatz. Dies bedeutet, dass für mindestens eine Kante die maximale Durchsatzrate erreicht wurde oder nach dem Entfernen dieses Pfadflusses kein Fluss mehr über diese Kante stattfindet. Beachten Sie, dass dies für die Periode $[i,j]$ $[t_i,t_j]$ . In beiden Fällen fließt kein Strom mehr durch diese Kante und wir können schließen, dass. $[t_{i+1},t_{j-1}]$ $|F_{s,t}| \leq m$

(*) Warum ist die vorherige Behauptung richtig? Nun, jeder andere Pfadfluss in beginnt vor und endet nach . Daher müssen sie sich zeitlich so überlappen, dass sie eine bestimmte Kante nutzen. Da der Durchsatz für den Pfadfluss maximiert ist, muss es eine Kante geben, an der er dicht ist. $F_{t_i,t_j}$ $t_{i+1}$ $t_{j-1}$

Daraus folgt , dass für eine Konstante und die Behauptung, dass es in NP ist, folgt. $\sum_{i,j \in [k]} | F_{i,j} |\leq c m^3$ $c$

Ruub
quelle

Für mich sieht die Zerlegungsgrenze fehlerhaft aus, ich werde versuchen, ein anschauliches Gegenbeispiel zu geben. Angenommen, das Netzwerk ist nur eine Quelle-> Senke-Flanke der Kapazität 100, Verzögerung 0, Lebensdauer 100. Betrachten Sie nun diesen Ablaufplan: im Zeitintervall [0, 1) senden Sie den Ablauf mit einer Rate von 1; in [1, 2] mit einer Rate von 2 usw. bis zu einer Rate von 100 in [99, 100]. Jede Zerlegung benötigt> = 100 Pfadflüsse, was Ihrer Behauptung widerspricht, wie ich es verstehe. Ich sollte erwähnen, dass Ford und Fulkerson dieses Hindernis in ihrer klassischen Lösung (ohne Lebensdauer) umgehen, indem sie eine bestimmte Art der optimalen Lösung in Betracht ziehen, keine willkürliche.

Daveagp

Dies kann wahrscheinlich vermieden werden, indem auch die "Lebensdauer" des Flusses maximiert wird, aber es gibt ein weiteres Problem im Beweis. Ich habe es überarbeitet, um es klarer zu machen.

Ruub

So wie ich es verstehe, müssten Sie nur eine Nummer pro Bogen speichern, die den Moment darstellt, in dem der Fluss durch den Bogen gesendet wird. Dies setzt voraus, dass der Lichtbogen danach unbrauchbar wird. Wenn der Lichtbogen andernfalls nach Beendigung der Verwendung wieder verwendet werden kann, sollte er Lösungen enthalten, die im zeitlichen Verlauf beliebig nahe an den Lösungen für den maximalen Durchfluss liegen (da der Durchfluss möglicherweise für eine beliebig kurze Zeit unterbrochen und dann erneut gepumpt wird) ).

Leandro M.
quelle

Ich kann nicht verstehen, was Ihre Behauptung ist.

Tsuyoshi Ito

Das halte ich nicht für richtig. Stellen Sie sich zum Beispiel ein Netzwerk mit drei Knoten vor, der Quelle s, dem Endgerät t und einem anderen Knoten v mit drei Bögen a1 = (s, v), a2 = (s, v), a3 = (v, t). Die Kapazitäten der Bögen sind alle 1, und die Fahrzeiten werden für a1 und a3 auf 0 und für a2 auf 100 eingestellt. Die Lebensdauer beträgt 1 für a1 und 1000 für a2 und a3. Dann kann man zum Zeitpunkt 0 eine Durchflusseinheit durch a1 und a3 von s nach t senden und beginnt, eine Durchflusseinheit durch a2 zu senden. Während der Zeit 1 bis 99 führt a3 keinen Fluss, da a1 weg ist, aber zum Zeitpunkt 100 kommt der Fluss durch a2 zu v und a3 wird erneut verwendet.

Yoshio Okamoto

Wenn ich das richtig verstehe, behaupten Sie teilweise, dass das verbleibende Problem mit dem klassischen Max-Flow-Over-Time-Ansatz gelöst werden kann, wenn die Geburts- / Todeszeiten der Kanten einmal festgelegt sind, aber ich verstehe nicht, wie dies der Fall ist.

Daveagp

@Yoshio: Wenn Sie in diesem Fall nicht sofort mit dem Senden einer Flow-Einheit entlang a2 beginnen, sondern nach einer willkürlich kurzen Zeitspanne, in der a1 erneut verwendet werden könnte, das Senden einer Flow-Einheit ganz einstellen und eine bessere Lösung erzielen würden.

Leandro M.

@ Dave: nein, das ist nicht genau das, was ich behaupte. Ich sage, dass entweder jeder Lichtbogen nur eine begrenzte Anzahl von Malen verwendet werden kann oder die Lösungen für das Problem die Lösungen für den maximalen Durchfluss über die Zeit beliebig approximieren sollten. Kurz gesagt, ich bin besorgt über die Details der Problemdefinition.

Leandro M.