Untergraph, der alle Knoten und Kanten enthält, die Teil längenbegrenzter einfacher st-Pfade in einem Digraphen sind

Hinweis: Ich habe eine ähnliche Frage zum ungerichteten Diagramm gestellt .

Gegeben

• Ein Digraph ohne Mehrfachkanten oder Schleifen$G$
• Ein Quellknoten $s$
• Ein Zielknoten $t$
• Maximale Pfadlänge $l$

Ich suche nach - Ein Teilgraph von G , der einen beliebigen Knoten und eine beliebige Kante in G enthält (und nur diejenigen), die Teil mindestens eines einfachen Pfades von s nach t mit einer Länge ≤ l sind .$G'$$G$$G$$s$$t$$\leq l$

Beachten Sie, dass ich die Pfade nicht aufzählen muss.

Wie die Frage gestellt wird, ist als Teil der Eingabe N P -hart. Dies folgt als Sonderfall der Klassifikation der Klasse von Mustern, für die das Problem des gerichteten Subgraphen-Homöomorphismus nach Fortune, Hopcroft und Wyllies Arbeit N P -vollständig ist: Das Problem des gerichteten Subgraphen-Homöomorphismus .$l$$\mathsf{NP}$$\mathsf{NP}$

Insbesondere ist das folgende Problem -vollständig: Gibt es bei einem gerichteten Graphen G und Eckpunkten s , t , v einen (einfachen) ( s , t ) -Pfad durch v ?$\mathsf{NP}$$G$$s,t,v$$(s,t)$$v$

Update: Diese Antwort scheint fehlerhaft zu sein. Siehe den Kommentar von Kristoffer Arnsfelt Hansen.

Ich weiß nicht, wie ich Ihr Problem lösen soll, aber hier ist eine Technik, um eine einfachere Version Ihres Problems zu lösen: Testen Sie bei gegebener Kante , ob es einen einfachen Pfad von s nach t gibt , der Kante e enthält . (Dies entspricht dem Sonderfall Ihres Problems mit l = ∞ .)$e$$s$$t$$e$$l=\infty$

Sie können dieses einfachere Problem lösen, indem Sie "Max-Flow mit unteren Grenzen" als Unterprogramm verwenden. Beim Standardproblem mit maximalem Durchfluss gibt uns die Kapazität jeder Kante eine Obergrenze für die Durchflussmenge, die durch diese Kante fließt, und wir fordern, dass die Durchflussmenge an der Kante durch 0 untergrenze ist. In "max-flow" mit Untergrenzen "dürfen wir sowohl eine Untergrenze als auch eine Obergrenze für den Durchfluss durch diese Kante angeben. Es ist bekannt, dass "Max-Flow mit Untergrenzen" in Polynomzeit gelöst werden kann.

Nehmen wir nun an, wir haben eine Kante und möchten testen, ob es einen einfachen Pfad von s nach t gibt , der die Kante e enthält . Wir werden einen Max-Flow mit Problem der unteren Grenzen einrichten. Nehmen Sie insbesondere den Graphen G und fügen Sie einen neuen Knoten s 0 mit der Kante s 0 → s und einen neuen Knoten t 1 mit der Kante t → t 1 hinzu . Stellen Sie die Kapazität (Obergrenze) für jede Kante 1 ein. Die Untergrenze für alle Kanten ist 0, mit der Ausnahme, dass die Untergrenze für Kante $e \in E$$s$$t$$e$$G$$s_0$$s_0 \to s$$t_1$$t \to t_1$$e$ist 1. Überprüfen Sie nun, ob es einen realisierbaren Fluss von nach t gibt , der alle Grenzen erfüllt (dieser Test kann, wie oben erwähnt, in Polynomzeit durchgeführt werden). Wenn es keinen Fluss gibt, gibt es keinen einfachen Weg von s nach t . Wenn es einen solchen Fluss gibt, ergibt das Verfolgen dieses Flusses einen einfachen Pfad von s nach t , der die Kante e enthält , so dass es einen so einfachen Pfad gibt.$s$$t$$s$$t$$s$$t$$e$

$e$

Ich habe diese Idee aus folgendem Artikel gelernt:

• Suchen eines einfachen Pfads mit mehreren Must-Include-Knoten . Hars Vardhan, Shreejith Billenahalli, Wanjun Huang, Miguel Razo, Arularasi Sivasankaran, Limin Tang, Paolo Monti, Marco Tacca und Andrea Fumagalli. Die Universität von Texas in Dallas, Technischer Bericht UTD / EE / 2/2009. Juni 2009.

(Lesen Sie unbedingt die Techreport-Version und nicht die veröffentlichte Version. Diese Idee finden Sie im zweiten Absatz der Einführung.)

$l$

Alternativ können wir Ihr Problem auf einfache Weise mithilfe der ganzzahligen linearen Programmierung (ILP) lösen. In der Praxis sind ILP-Löser bei vielen Problemen ziemlich gut. Ihre Worst-Case-Laufzeit ist jedoch immer noch exponentiell, sodass kein Algorithmus mit einer polynomiellen Worst-Case-Laufzeit erhalten wird. Lassen Sie mich wissen, ob ich erläutern soll, wie dies mit ILP formuliert werden kann.

$G$$O(V + E)$

$s$$G$$d_s(v)$$v$$G$$s$$v$$t$$G$$(v,u)$$(u,v)$$G$$d_t(v)$$v$$G$

$v$$s$$t$$v$$d_s(v) + d_t(v)$

$G'$$v$$G$$d_s(v) + d_t(v) \leq l$$(u,v)$$d_s(u) + d_t(v) \leq l-1$

$l$$O(2^l\cdot m(n+m))$$l$

$m$$l$$e$

Foreach $e=(u,v)\in E$: 
a. do for $O(2^l)$ times:
  1. Compute a random partition of the vertices set $V=(S,V\setminus S)$ 
   such that $s,u\in S$, $v,t\not \in S$ (and every other vertex is in $S$ w.p. 1/2).
  2.Find the shortest path from $s$ to $u$ in the subgraph induced by $S$.
    And the shortest path from $v$ to $t$ in the subgraph of $V\setminus S$. 
  3.If the sum of distances is no more than $l-1$, add $e$ to the output graph.

$\leq l$$G$$e$

$u$$S$$V\setminus S$$2^{-l}$$O(2^l)$

Derandomisierung

$2^{polylog(l)}$

$(n,l)$$S$$O(2^{l+ log^3(l)}\cdot poly(n))$