Ist es nicht einfacher, die Transitivität eines Digraphen zu überprüfen, als (in Bezug auf die asymptotische Komplexität) den transitiven Verschluss des Digraphen vorzunehmen? Kennen wir eine Untergrenze besser als um festzustellen, ob ein Digraph transitiv ist oder nicht?
9
Antworten:
Im Folgenden werde ich Folgendes zeigen: Wenn Sie einen O ( ) - Zeitalgorithmus haben, um zu überprüfen, ob ein Graph für ein transitiv ist , dann haben Sie ein O ( ) Zeitalgorithmus zum Erkennen eines Dreiecks in einem Knoten-Diagramm, und daher hätten Sie (nach einem Artikel aus FOCS'10 ) einen O ( ) -Zeitalgorithmus zum Multiplizieren von zwei boolesche Matrizen, und daher impliziert dies nach einem Ergebnis von Fischer und Meyer aus den 70er Jahren auch einen O ( ) -Zeitalgorithmus für den transitiven Abschluss. ε > 0 n 3 - ε n n 3 - ε / 3 n × n n 3 - ε / 3n3−ε ε>0 n3−ε n n3−ε/3 n×n n3−ε/3
Angenommen, Sie möchten ein Dreieck in einem Knoten G erkennen . Wir können nun das folgende Diagramm H erstellen . H ist dreigliedrig mit Partitionen I , J , K auf jeweils n Knoten. Hier wird jeder Knoten x von G hat Kopien x I , x J , x K in den Teilen I , J , K . Fügen Sie für jede Kante ( u , v ) von G gerichtete Kanten hinzu (n G H H I,J,K n x G xI,xJ,xK I,J,K (u,v) G und ( u J , v K ) . Addieren Sie für jede Nichtkante ( u , v ) von G die gerichtete Kante ( u I , v K ) .( uich, vJ.) ( uJ., vK.) ( u , v ) G ( uich, vK.)
Erstens, wenn ein Dreieck u , v , w enthält , dann ist H nicht transitiv. Dies liegt daran, dass die Kanten ( u I , v J ) , ( v J , w K ) in H sind , ( u I , w K ) jedoch nicht. Zweitens muss, wenn H nicht transitiv ist, ein gerichteter Pfad von einem Knoten s zu einem Knoten t in H existieren, so dass (G u , v , w H. ( uich, vJ.) , ( vJ., wK.) H. ( uich, wK.) H. s t H. ist nicht eine gerichtete Kante in H . Die längsten Pfade in H haben jedoch zwei Kanten, und daher muss ein solcher Pfad die Form ( u I , v J ) , ( v J , w K ) und ( u I , w K ) haben , daherist er nicht in H. u , v , w bilden in G ein Dreieck.( s , t ) H. H. 2 ( uich, vJ.) , ( vJ., wK.) ( uich, wK.) H. u , v , w G
quelle
Es sieht so aus, als ob die bekannteste Untergrenze ist, da jede Untergrenze eine Untergrenze für die Boolesche Matrixmultiplikation impliziert. Wir wissen, dass die Transitivitätsprüfung mit einer Booleschen Matrixmultiplikation erreicht werden kann, dh G ist genau dann transitiv, wenn G = G 2 ist .Ω(n2) G G=G2
quelle
Es ist genauso schwer herauszufinden, ob eine DAG transitiv ist, wie zu entscheiden, ob ein allgemeiner Digraph transitiv ist (was uns zu Ihrer vorherigen Frage zurückbringt :)).
Angenommen, Sie haben einen Algorithmus, der in der Zeit um zu entscheiden, ob eine DAG transitiv ist.O(f(n))
Bei einem gerichteten Graphen können Sie den folgenden zufälligen Algorithmus verwenden, um zu entscheiden, ob G in der Zeit O ( f ( n ) ⋅ log ( 1 ) transitiv istG G und Fehlerwahrscheinlichkeit≤δ:O(f(n)⋅log(1δ)) ≤δ
Nun ist es offensichtlich, dass, wenn transitiv war, dieser Algorithmus true zurückgibt.G
Nehmen wir nun an, war nicht transitiv. Sei e 1 = ( v i , v j ) , e 2 = ( v j , v k ) ∈ E, so dass ( v i , v k ) ∉ E (es muss Kanten geben, da G nicht transitiv ist). Die Wahrscheinlichkeit, dass e 1 , e 2 ∈ G ' ist , ist 1G e1=(vi,vj),e2=(vj,vk)∈E (vi,vk)∉E G e1,e2∈G′ , daher ist in jeder Iteration die Wahrscheinlichkeit, dass der AlgorithmusGnicht transitiv darstellt,116 G und nachO(log(δ)) -Iterationen beträgt die Ausfallwahrscheinlichkeit höchstensδ.16 O(log(δ)) δ
quelle
Ich denke, dies sollte in linearer Zeit möglich sein, dh wobei n die Anzahl der Eckpunkte und m die Anzahl der Kanten ist. Vielleicht durch Anpassen eines Diagrammdurchlaufschemas an die gerichtete Einstellung? Ein Ausgangspunkt könnte das hier beschriebene LexBFS / LexDFS sein ; Für gerichtete Graphen sollten wir eher die topologische Sortierung als die DFS verwenden. Vielleicht ist es also mit einem LexTSA- Algorithmus möglich, dies zu entdecken?O(n+m) n m
quelle
In Bezug auf die vorherige Antwort ist hier eine einfache Möglichkeit, einen solchen Algorithmus zu definieren. Weisen Sie jedem Scheitelpunkt einen Index i ( x ) zu , der auf 0 initialisiert ist . Für jedes x sei M ( x ) das Multiset von Indizes seiner Nachbarn. Wir simulieren eine topologische Sortierung, indem wir eine Menge R unerforschter Eckpunkte beibehalten , die auf die gesamte Menge initialisiert sind. Bei jedem Schritt machen wir Folgendes:x i(x) 0 x M(x) R
Wählen Sie einen Scheitelpunkt dessen Multiset M ( x ) minimal ist (in der Multiset-Reihenfolge);x∈R M(x)
Aktualisieren auf den aktuellen Schleifenzähler und entfernen x aus R .i(x) x R
Kann dieser Algorithmus für Ihr Problem oder für eine andere Anwendung verwendet werden?
quelle