Untergraph mit allen Knoten und Kanten, die Teil längenbegrenzter einfacher st-Pfade in einem ungerichteten Graphen sind

Ganz ähnlich zu meiner zuvor geposteten Frage . Diesmal ist das Diagramm jedoch ungerichtet.

Gegeben

• Ein ungerichteter Graph $G$ ohne Mehrkanten oder Schleifen,
• Ein Quellscheitel ,$s$
• Ein Zielscheitelpunkt ,$t$
• Maximale Weglänge $l$ ,

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

Anmerkungen:

• Ich muss die Pfade nicht aufzählen.
• Ich suche einen effizienten Algorithmus (sowohl Zeit als auch Speicher), da ich ihn über sehr große Graphen ausführen muss (10 ^ 8 Eckpunkte, 10 ^ 9 Kanten).

Nun, das Problem ist immerhin in Ich werde die vorherige Antwort behalten , da sie auch für den gerichteten Fall (der NPC ist, wie bei der anderen Frage beantwortet) funktioniert und zeigt, dass es sich um F P T in Bezug auf l handelt .$P$$FPT$$l$

Im ungerichteten Fall ist es lösbar, deterministisch über den minimalen Kostenfluss (dies funktioniert möglicherweise nicht auf den Skalen, auf die Sie sich in der Frage beziehen, aber es ist besser als der exponentielle Algorithmus.

Die folgende Prozedur entscheidet, ob eine Kante ein Teil des Ausgabegraphen sein soll. Um das ursprüngliche Problem zu lösen, schleifen Sie einfach über alle Kanten.$e=(u,v)\in E$

Gehen Sie wie folgt vor, um das Flow-Netzwerk zu erstellen:

Schritt 1: Erweitern einen Scheitelpunkt zu haben , x e und ersetzen e mit den Kanten ( u , x e ) , ( x e , u ) , ( v , x e ) , ( x e , v ) (sie als einen gerichteten Teil des Verkehrsnetzes), setzen Sie ihre Kosten auf 0.$e$$x_e$$e$$(u,x_e),$$(x_e,u),(v,x_e),(x_e,v)$

Schritt 2: Ersetzen Sie jeden Scheitelpunkt mit Ausnahme von x e durch zwei Scheitelpunkte t - und t + und fügen Sie eine Kante ( t - , t + ) hinzu . Setzen Sie die Kosten für diese Kanten auf 1.$t$$x_e$$t^-$$t^+$$(t^-,t^+)$

Schritt 3: Ersetzen Sie jede Kante durch die Kanten ( a + , b - ) , ( b + , a - ) . Setzen Sie die Kosten dieser Kanten auf 0.$\{a,b\}\in E$$(a^+,b^-),(b^+,a^-)$

Schritt 4: Fügen Sie einen neuen Eckpunkt und fügen Sie die Kanten ( s , y e ) , ( t , y e ) mit den Kosten 0 hinzu.$y_e$$(s,y_e),(t,y_e)$

Schritt 5: Stellen Sie alle Kapazitäten auf 1 ein.

Führen Sie nun den Min-Cost-Flow-Algorithmus aus und suchen Sie nach einem Fluss von Wert 2 von nach y e .$x_e$$y_e$

Analyse:

• Jeder 2-wertige Fluss von bis y e ist eine Vereinigung von einem Pfad x e ⇝ s → y e und einem Weg x e ⇝ t → y e .$x_e$$y_e$$x_e\leadsto s\to y_e$$x_e\leadsto t\to y_e$
• Die Pfade sind disjunkt, da für jeden Scheitelpunkt nur 1 Kapazität im Bogen ( t - , t + ) vorhanden ist .$t$$(t^-,t^+)$
• Die zurückgegebenen Pfade sind die beiden Pfade, deren Summe der Entfernungen minimal ist, und das sind auch die Kosten des gefundenen Flusses. Dies ermöglicht es uns, zum Ausgabediagramm hinzuzufügen oder auf andere Weise zu löschen.$e$

Hier ist eine falsche Antwort: Es werden einige Eckpunkte ausgegeben, die Teil nicht einfacher Pfade von nach t sind und die nicht Teil eines einfachen Pfades von s nach t mit der Länge ≤ ℓ sind . Die Antwort ist möglicherweise immer noch relevant für die Bewerbung des Fragestellers. Deshalb lasse ich sie hier.$s$$t$$s$$t$$\le \ell$

Hier ist ein Algorithmus, der in der Zeit abläuft (und tatsächlich schneller ist als dies, wenn ℓ klein ist).$O(|V|+|E|)$$\ell$

Der Algorithmus führt eine BFS-Suche von , die in der Tiefe ℓ endet . Dieses BFS gibt eine Menge V s aller Scheitelpunkte an, die von s mit einem Längenpfad von höchstens ℓ erreichbar sind , und berechnet auch die Abstände d i s t ( s , v ) für jedes v ∈ V s . Dann würde ich dasselbe von t machen und die Menge V t und die Entfernungen von t erhalten . Schließlich sind die Eckpunkte, nach denen Sie suchen, genau V s o l $s$$\ell$$V_s$$s$$\ell$$dist(s,v)$$v \in V_s$$t$$V_t$$t$. Die Kanten sind genau diejenigen Kanten inE[ V s o l u t i o n ](=(v,u$V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$$E[V_{solution}]$ ).$=(v,u) \in E : u,v \in V_{solution}$

Die Laufzeit dieses Algorithmus ist sicherlich weil er nur zwei BFSs ausführt. Die Laufzeit ist jedoch tatsächlich O ( | V s | + | V t | + | E [ V s ] | + | E [ V t ] | ), was viel kleiner ist als die Größe des Graphen, wenn der ℓ- Radius Nachbarschaften von s und $O(|V|+|E|)$$O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$$\ell$$s$$t$ sind klein.

Edit: In der Praxis gibt es wahrscheinlich einen etwas schnelleren Algorithmus, der ein BFS aus und t der Tiefe nur ℓ / 2 anstatt ℓ ausführt . Dadurch werden alle Pfade entdeckt, und mit ein wenig Buchhaltung können Sie alle Scheitelpunkte finden. Dies verkürzt die Laufzeit durch eine Quadratwurzel für den Fall eines großen Zufall aussehenden Graphen , wenn l klein ist.$s$$t$$\ell/2$$\ell$$\ell$

Dies ist als Kommentar gedacht, aber es ist zu lang, um einen Kommentar zu verfassen.

Möglicherweise interessieren Sie sich auch für Diagrammschlüssel oder Emulatoren für Ihre Zwecke. Ein Schraubenschlüssel eines Graphen ist ein Teilgraph H = ( V , E ' ) mit wenigen Kanten, aber ungefähr erhaltenen Abständen. Ein Emulator ist ein Graph H = ( V , E ' , w ), dessen Kanten gewichtet werden dürfen.$G = (V, E)$$H = (V, E')$$H = (V, E', w)$

$O(n^{4/3})$$O(n^{4/3})$$O(n^{4/3})$

Wenn das nützlich klingt, kann ich versuchen, die relevanten Konstruktionen für Sie zu graben.