Route Existenz zwischen n Knotenpaaren

Wie kann man bei einem gerichteten azyklischen Graphen mit Knoten bestimmen, ob es einen Pfad zwischen einem der folgenden n Knotenpaare gibt ? Es gibt einen einfachen Algorithmus in (wobei m die Anzahl der Kanten ist), indem von jedem Knoten gesucht wird , aber kann es besser gemacht werden?( 1 → n + 1 ) , … , ( n → n + n ) O ( n ⋅ ( n + m ) ) 1 … $2n$$(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$$O(n \cdot (n + m))$$1 \ldots n$

EDIT: Ich suche Existenz, nicht vollständige Pfade.

Wie Chandra Chekuri in einem Kommentar betonte, könnten Sie den transitiven Abschluss einfach durch schnelle Matrixmultiplikation berechnen und das Problem in O ( ) (verwenden Sie Ihre Lieblingsmethode, O ( ) über Coppersmith und Winograd oder praktischer mit Straßens O ( )), und dies wäre gut für dichte Graphen.n 2,376 n $n^\omega$$n^{2.376}$$n^{2.81}$

Nun behaupte ich, wenn Sie diese Laufzeit für Ihr Problem für dichte Graphen übertreffen könnten, würden Sie einen Algorithmus für die Dreieckserkennung erhalten, der effizienter ist als die Berechnung des Produkts zweier Boolescher Matrizen. Die Existenz eines solchen Algorithmus ist ein großes offenes Problem.

Ich werde das Dreiecksproblem auf das Problem der Erreichbarkeit von n-Paaren-DAG reduzieren. Angenommen, wir erhalten einen Graphen G auf n Knoten und möchten bestimmen, ob G ein Dreieck enthält.

Erstellen Sie nun aus G eine DAG G 'wie folgt. Erstellen Sie vier Kopien der Scheitelpunktmenge , V 2 , V 3 , V 4 . Fügen Sie für Kopien u i ∈ V i , v i + 1 ∈ V i + 1 für i = 1 , 2 , 3 eine Kante ( u i , v i + 1 ) hinzu, wenn ( u , v $V_1$$V_2$$V_3$$V_4$$u_i\in V_i$$v_{i+1}\in V_{i+1}$$i=1,2,3$$(u_i,v_{i+1})$$(u,v)$war in G. Wenn wir nun fragen, ob es einen Pfad zwischen einem der Paare für alle u ∈ G gibt, dann würde dies genau fragen, ob es in G ein Dreieck gibt . Der aktuelle Graph hat 4 n Knoten und wir fragen nach n Paaren. Wir können jedoch 2 n isolierte Dummy-Knoten hinzufügen und stattdessen 3 n Abfragen haben (indem wir eine Abfrage für 2 n verschiedene Paare ( y , d ) hinzufügen , wobei y ∈ V $(u_1, u_4)$$u\in$$G$$4n$$n$$2n$$3n$$2n$$(y,d)$ und d ein Dummy), wodurch eine 6 n- Knoten-Instanz genau Ihres Problems erhalten wird.$y\in V_2\cup V_3$$d$$6n$

Die topologische Sortierung ( ) arbeitet dann daran, ein Bit-Set von Knoten zu verbreiten, von denen aus jeder Knoten erreicht werden kann ( O ( m n ) ).$O(m+n)$$O(m n)$

Nach der topologische Sortierung können Sie tun , Schnell Ablehnung (wenn der Knoten n + x , bevor der Knoten kommt x in der Art , dann gibt es keinen Weg von x nach n + x ).$O(n)$$n+x$$x$$x$$n+x$

$O(N^2)$

yespath = array(1..N)       // output of the algorithm
                            // initially filled with false
processed = array(1..N)     // processed nodes

// HEURISTIC 1: some preprocessing
for every node u in 1..N
  if (no outbound edges from u) then processed[u] = true
  if (no inbound edges to u+N) then processed[u] = true

for each node u in [1..N]    // MAIN loop 
  if (not processed[u]) then
    collected = [u]          // a list that initially contains u
    visited = array(1..2*N)  // filled with zeroes        
    do a breadth first scan from u
       for each node v found in the search
         set visited[v] = distance from u
         if (v <= N) then add v to collected
    end do

    // HEURISTIC 2: useful collected info on other nodes <= N
    foreach node v in collected
      processed[v] = true
      if ( visited[ v + N ] > 0 and visited[v] < visited[v+N] ) then yespath[v] = true
    end foreach

  end if
end for // MAIN loop

$O(N^2)$$O(N*k)$$e > u + N$

Andere Heuristiken können hinzugefügt werden, aber ihre Effizienz (und Effizienz der drei vorgeschlagenen) hängt stark von der Graphstruktur ab.