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

12

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 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).
Lior Kogan
quelle
Schau es dir an. Wir haben dieses Papier gefunden, das eine ähnliche Reduzierung des minimalen Kostenflusses zu bewirken scheint, aber die speziellen Eigenschaften des Netzwerks nutzt, um es schneller als die allgemeinen MCF-Algorithmen zu lösen.
RB

Antworten:

6

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 .PFPTl

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)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.exee(u,xe),(xe,u),(v,xe),(xe,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.txett+(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}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.ye(s,ye),(t,ye)

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 .xeye


Analyse:

  • Jeder 2-wertige Fluss von bis y e ist eine Vereinigung von einem Pfad x es y e und einem Weg x et y e .xeyexesyexetye
  • 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
RB
quelle
1
Es ist einfacher, das Argument in der obigen Antwort zu verstehen, indem die Reduktion auf gerichteten Fluss weggenommen wird. Es gibt einen einfachen Pfad von nach t , der einen Knoten v enthält, wenn es einen Pfad P von v nach s und einen Pfad Q von v nach t gibt, so dass P und Q mit Ausnahme von v knotendisjunkt sind . Dies nutzt die Ungerichtetheit entscheidend aus. Dies kann über den Flow überprüft werden und die Kostenversion kann auch über den Min-Cost-Flow erfolgen. Man kann prüfen, ob es einen einfachen Weg von s nach t gibt , der e enthältstvPvsQvtPQvstedurch Einführen eines Knotens in der Mitte von . e
Chandra Chekuri
@ChandraChekuri - das ist richtig, aber denken Sie daran, dass es einen viel einfacheren Algorithmus für die Entscheidung gibt, wenn das Problem nicht die Längenbeschränkung hat - siehe hier
RB
Klar, ich kenne diese Lösung auch - konzeptionell ist es gut, zweifach verbundene Komponenten über getrennte Pfade zu verstehen, obwohl man Schnittpunkte und zweifach verbundene Komponenten direkt über DFS finden kann.
Chandra Chekuri
@ RB: Danke. Der vorgeschlagene Algorithmus kann wirksam sein, wenn l relativ groß ist, ist aber wahrscheinlich für relativ kleine Werte von l suboptimal. Ich schätze, ich kann G zuerst trimmen, indem ich einen Scheitelpunkt, der weiter als der Boden (l / 2) von s und die Decke (l / 2) von t entfernt.
Lior Kogan
1
Versuchen Sie, den sukzessiven Algorithmus für kürzeste Pfade anzupassen (der hier auch als Surballe-Algorithmus für den Fall von 2 Pfaden bezeichnet wird). Sie möchten kürzeste 2-Wege von (es ist besser, es y anstelle von y e zu nennen, da es für alle Kanten gleich ist) zu jedem x e finden . Ich denke, dies ist effizient möglich, indem zuerst ein Baum mit dem kürzesten Pfad aus y berechnet und dann die Berechnung des zweiten Pfads mit einiger Sorgfalt implementiert wird. yyyexey
Chandra Chekuri
1

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.stst

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

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 usVssdist(s,v)vVstVtt. Die Kanten sind genau diejenigen Kanten inE[ V s o l u t i o n ](=(v,u)Vsolution={v:vVsVt,dist(s,v)+dist(t,v)}E[Vsolution] ).=(v,u)E:u,vVsolution

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 tO(|V|+|E|)O(|Vs|+|Vt|+|E[Vs]|+|E[Vt]|)st 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.st/2

Mobius Knödel
quelle
3
Dies zwingt den Pfad nicht dazu, einfach zu sein. Betrachten Sie den einfachen Pfadgraphen und l = 4 . Sie werden v als Teil der Ausgabe zurückgeben, obwohl es keinen einfachen Pfad gibt, der v durchläuft ...tusvxl=4vv
RB
Danke für die Korrektur @RB. Ich habe meine Antwort bearbeitet und festgestellt, dass sie falsch ist.
Möbius Knödel
1

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(n4/3)O(n4/3)O(n4/3)

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

GMB
quelle