Aufzählung aller Paare disjunkter Pfade

10

Bei einem gerichteten Graphen und die zwei Scheitel . Ein Paar einfacher Pfade von nach ist kantendisjunkt, wenn sie keine Kante teilen. $G = (V,E)$ $s,t \in V$ $p_1,p_2$ $s$ $t$

Bei Verwendung des maximalen Durchflusses ist es leicht zu entscheiden, ob es ein Paar von disjunkten Kantenpfaden von nach . Gibt es nun einen polynomiellen Zeitverzögerungsalgorithmus, um alle Paare von kantendisjunkten Pfaden von nach ? $s$ $t$ $s$ $t$

cc.complexity-theory graph-algorithms Amateur
quelle

1

Nein, da es möglicherweise exponentiell viele solcher Pfade gibt.

Kaveh

6

@Kaveh: Ich denke, ein "Polynomverzögerungsalgorithmus" darf exponentiell lange dauern, solange die Verzögerung zwischen den Ausgängen polynomiell lang ist. Zum Beispiel gibt es einen Polynomverzögerungsalgorithmus, der alle maximalen Cliquen in aufsteigender Reihenfolge auflistet, obwohl die Anzahl der maximalen Cliquen exponentiell ist.

Robin Kothari

3

Ist es möglich, die Erklärung der Polynomverzögerung in die Frage aufzunehmen? Ich war damit nicht vertraut, bis ich Robins Kommentar gelesen hatte.

Artem Kaznatcheev

@Robin, du hast recht, ich habe nicht auf das Wort "Verzögerung" geachtet.

Kaveh

6

Ich glaube, Artem Kaznatcheevs Antwort ist richtig, aber sie gibt keinen Polynomraum. Hier ist also ein anderer Ansatz, der in dieser Hinsicht etwas besser funktionieren sollte.

Mit dem maximalen Durchfluss ist es möglich, ein etwas allgemeineres Problem zu lösen: Suchen Sie ein Paar von nicht zusammenhängenden Kantenpfaden von zwei Scheitelpunkten {s1, s2} zu einem anderen Scheitelpunktpaar {t1, t2}, ohne jedoch zu steuern, welcher Quellscheitelpunkt verbunden ist zu welchem Zielscheitelpunkt.

Angenommen, wir haben einen Graphen G und Eckpunkte s1, s2, t1, t2, für die wir alle Pfadpaare auflisten möchten. Suchen Sie ein einzelnes Pfadpaar P1, P2 und lassen Sie e = (s1, v) die erste Kante auf einem dieser Pfade sein. Dann können wir den Problemraum in zwei Teilprobleme aufteilen: Die Pfadpaare, die e verwenden, sind dieselben wie die Pfade von {v, s2} bis {t1, t2} in G-s1 und die Pfadpaare, die nicht verwendet werden e sind die gleichen wie die Pfade von {s1, s2} zu {t1, t2} in Ge. Wiederholen Sie diese beiden Teilprobleme und melden Sie (um Doppelarbeit zu vermeiden) nur dann einen Pfad, wenn Sie sich am Ende der Rekursion befinden.

David Eppstein
quelle

1

Ist es offensichtlich, dass der Algorithmus eine Polynomverzögerung ist, wenn wir bis zum Ende der Rekursion warten?

Artem Kaznatcheev

Die Rekursion benötigt polynomiell viele Ebenen, um einen Tiefpunkt zu erreichen (da jede Ebene etwas aus dem Diagramm löscht), und jeder Zweig kehrt entweder sofort zurück (weil er kein Pfadpaar finden kann) oder führt einen Tiefpunkt aus und gibt etwas zurück, also ja, es dauert nur polynomial Verzögerung.

David Eppstein

5

Dies ist das erste Mal, dass ich über Polynomverzögerungsalgorithmen gelesen habe, daher bin ich mir meiner Antwort nicht 100% sicher, aber ich denke, dass so etwas wie das Folgende funktionieren sollte.

$<$ $D$ $G$

$F$

$F(s,t,G, ^*D)$

$^*D$ $D$

$(P,Q)$ $P < Q$ $s$ $t$
$(P,Q)$ $D$

$(P,Q)$ $D$

$uv \in E(P\cup Q)$ $F(s,t,G - \{uv\}, ^*D)$

$D$ $s,t \in V(G)$ $s < t$ $s \neq t$ $F(s,t,G,*D)$

$PSPACE$ $PSPACE$

Artem Kaznatcheev
quelle

2

$O(m)$

Rui Ferreira
quelle

Aufzählung aller Paare disjunkter Pfade

Antworten: