Finden von mindestens zwei Pfaden gleicher Länge in einem gerichteten Graphen

20

Angenommen , wir haben ein gerichteter Graph und zwei Knoten und . Ich würde gerne wissen, ob es bereits Algorithmen zur Berechnung des folgenden Entscheidungsproblems gibt:G=(V,E)AB

Gibt es mindestens zwei Pfade zwischen und gleicher Länge?AB

Wie steht es mit der Komplexität? Kann ich es in polynomialer Zeit lösen?


Ich möchte dem Diagramm eine neue Einschränkung hinzufügen, da das Problem möglicherweise besser lösbar ist. In der Adjazenzmatrix ist nicht jede Spalte leer. Jeder Knoten hat also mindestens einen Pfeil am Eingang und es ist auch mindestens ein Knoten mit sich selbst verbunden. Wenn also der Knoten der te Knoten ist, dann ist eine Kante im Graphen.i(i,i)

Paolo Parisen T.
quelle
Meinten Sie einfache wege? (Jeder Knoten darf höchstens einmal besucht werden.) Dürfen sie auch einen gemeinsamen internen Knoten haben?
1
Nein, es gibt keine Einschränkungen für Pfade. Sie können eine Schleife ausführen, wenn Sie möchten.
Paolo Parisen T.
Einfache Beobachtung ist dies: Wenn es nur einen einfachen Pfad zwischen gibt und dieser einfache Pfad mit höchstens einer Schleife verbunden ist, können Sie einfach sagen . Wenn mindestens zwei Schleifen unterschiedlicher Länge mit diesem einfachen Pfad verbunden sind , Sie könnten ja sagen, ... (Ich denke, ähnliche Dinge sind nützlich und Sie könnten es beweisen), aber im Fall von unzusammenhängenden einfachen Pfaden (wenn Sie dabei auf unzusammenhängende einfache Pfade gestoßen sind), ist es ein NPC. N oA,BNo
1
@mrm: Ich sehe das nicht als Duplikat. Nach allen Wanderungen zu fragen ist eine sehr zeitaufwendige Operation (im Allgemeinen gibt es unendlich viele Wanderungen), wohingegen das OP nach zwei (einfachen) Wegen fragt , nicht nach allen Wanderungen.
Dave Clarke

Antworten:

10

Betrachten wir einen Graphen , möchten wir wissen, ob es zwei verschiedene Pfade von A nach B mit der gleichen Länge gibt. Was ist zu tun? Einfach: Code zwei Pfade in einem. Definieren Sie den Graphen G ' mit den Eckpunkten V × V × { 0 , 1 } . Sie machen einen Schritt in G ', indem Sie zwei unabhängige Schritte in G machen . Das zusätzliche Bit zeigt an, ob die beiden Pfade bereits voneinander getrennt wurden.GABGV×V×{0,1}GG

Formal gibt es eine Kante in G ', wenn i i ' , j j ' in G und e ' = e ( i , i ') ) ( j , j ) .(i,j,e)(i,j,e)GiijjGe=e(i,i)(j,j)

Der Algorithmus prüft, ob ein Pfad vorhanden ist in G ' ( A , A , 0 ) zu ( B , B , 1 ) gibt , der O ( V 4 ) oder so etwas wie O ( ( V + E ) 2 ) ist .(A,A,0)(B,B,1)GO(V4)O((V+E)2)

Wenn Sie zustimmen, dass dieser Algorithmus korrekt ist, ist der Pfad in folglich höchstens 2 n 2 lang , daher müssen mögliche "Pfadkollisionen" spätestens bei dieser Länge auftreten. Aus dieser Beobachtung können Sie einen O ( V ω log V ) -Algorithmus erhalten, wobei ω die Komplexität der Matrixmultiplikation ist (fragen Sie, ob Sie einen Spoiler benötigen ...).G2n2O(VωlogV)ω

Ich bin der festen Überzeugung, dass es einen -Algorithmus gibt, der mehr von der Struktur des Problems Gebrauch macht.O(V+E)

sdcvvc
quelle
3
Das ist elegant.
Raphael
4

Wahrscheinlich habe ich eine Antwort auf dieses Problem, aber ich bin nicht sicher, ob es funktioniert.

Es ist nicht wichtig, die beiden Pfade zu "finden", sondern nur zu "wissen", ob sie existieren oder nicht. Ich denke nicht, dass dies ein NP-vollständiges Problem ist.

So nehmen Sie die Adjazenzmatrix . Wir können leicht annehmen, dass es mit einem Wert von 0,1 gefüllt ist. (0 = keine Kante; 1 = es gibt eine Kante) Verwenden wir die folgende Algebra mit 3 Werten (0,1,2), wobei alles wie gewohnt funktioniert, außer: 2 + <etwas> = 2 ; 2 <was auch immer größer als 0> = 2 istA2+<something>=22<whatever greater than 0>=2

Also, wenn es zwei Wege von gleicher Länge von ich erwarte , dass es ein Wert p derart , dass ( A p ) i , j = 2 .i,jp(Ap)i,j=2

Sei die Anzahl der Eckpunkte im Graphen (oder sagen wir, dass A die Dimension n × n hat ). Ich kenne den Wert von p nicht , aber wenn ich A durch Multiplikation mit sich selbst für höchstens iterierenAn×npAsollte ich die Antwort finden. (also, p < n 2 ) (der Sinn ist, dass ich A überprüfe, dann überprüfe ich A 2 , dann überprüfe ich A 3 und so weiter ...)n2p<n2AA2A3

Hier ist meine Argumentation:

  • Wenn die beiden Pfade einfache Pfade sind, funktioniert es. wenn ja, muss ich höchstens mal iterieren .n
  • Wenn es mindestens einen neasted Zyklus gibt oder es einen Pfad mit zwei Zyklen gibt, muss ich das kleinste gemeinsame Vielfache (LCM) finden. ist sicher ein größerer Wert und in weniger als n 2 Mal, wenn es gibt, sollte ich sie finden müssen.n2n2
  • Wenn die beiden Pfade zwei unterschiedliche Pfade sind, beide mit einem Zyklus, dann ist es mehr oder weniger ähnlich, eine Lösung für diese beiden Gleichungen zu finden: , wobei m und k die Länge dieser beiden unterschiedlichen Pfade sind Fahrräder. Die oben definierte Matrixmultiplikation A q besagt: "Gibt es einen Pfad von i nach j, dessen Länge q ist ?" Wenn A q also größer als 1 ist , bedeutet dies, dass es mehr Pfade gibt, die von i nach j führen . Durch Iteration der Matrix nα+βm=γ+δkmkAqijqAq1ij mal durchlaufen wir alle möglichen Kombinationen von δ und β . Tatsächlich L C M ( a , b ) definiert ist als ( ein * b ) / G C D ( a , b ) und kein Zyklus können größer sein n .n2δβLCM(a,b)(ab)/GCD(a,b)n

Ich höre auf zu iterieren, sobald ich .(Ap)i,j=2

Liege ich falsch?

Paolo Parisen T.
quelle
Ich habe dasselbe versucht und bin auf einige Probleme / Ungewissheiten gestoßen: 1) Was ist, wenn die Pfade mit mehr als einem Zyklus verbunden sind? Müssen Sie alle Kombinationen "überprüfen" (im schlimmsten Fall liegt jeder Knoten in exponentiell vielen Zyklen!), Die obere Schranke sprengen, oder ist es ausreichend, nur eine für jede zu berücksichtigen? 2) Ist die LCM aufgrund der konstanten Offsets und γ wirklich eine Obergrenze? αγ
Raphael
Eine funky Algebra ist übrigens nicht erforderlich: Stoppen Sie einfach, sobald Sie eine als Matrixeintrag berechnen . 2
Raphael
@Raphae 1) Wenn es einen Pfad mit zwei Zyklen gibt, dann gibt es mit Sicherheit zwei Pfade gleicher Länge. eine, die sich beim ersten Zyklus wiederholt, und eine, die sich beim zweiten Zyklus wiederholt. wie viel müssen sie schleifen? genau die LCM der Länge beider Zyklen. Dies ist durch , wobei n die Anzahl der Scheitelpunkte im Diagramm ist. 2) LCM ist die Obergrenze (im Fall 1)), weil LCM (a, b) durch a * b plus α- und γ- Offsets begrenzt ist; Insgesamt haben wir also L C M (n2nαγLCM(a,b)+α+γ<ab+α+γ. wir wissen, dass , also ist a b + α + γ kleiner als n 2 . α+γ+a+b<nab+α+γn2
Paolo Parisen T.