Ruta de existencia entre n pares de nodos

Dado un gráfico acíclico dirigido con nodos, ¿cómo se puede determinar si hay una ruta entre alguno de los siguientes n pares de nodos ? Hay un algoritmo simple en (donde m es el número de aristas) haciendo una búsqueda desde cada nodo , pero ¿se puede hacer mejor?$2n$O ( n ⋅ ( n + m ) ) 1 … $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$$O(n \cdot (n + m))$$1 \ldots n$

EDITAR: Estoy buscando existencia, no caminos completos.

Como Chandra Chekuri señaló en un comentario, podría calcular el cierre transitivo a través de una multiplicación de matriz rápida, resolviendo el problema en tiempo O ( ) (use su método favorito, O ( n 2.376 ) a través de Coppersmith y Winograd, o más prácticamente usando Strassen's O ( n 2.81 )), y esto sería bueno para gráficos densos.$n^\omega$$n^{2.376}$$n^{2.81}$

Ahora, afirmo que si puede superar este tiempo de ejecución para su problema de gráficos densos, obtendría un algoritmo para la detección de triángulos que es más eficiente que calcular el producto de dos matrices booleanas. La existencia de tal algoritmo es un gran problema abierto.

Reduciré el problema del triángulo al problema de n-pares-DAG-accesibilidad. Supongamos que se nos da un gráfico G en n nodos y queremos determinar si G contiene un triángulo.

Ahora, desde G cree un DAG G 'de la siguiente manera. Cree cuatro copias del conjunto de vértices, , V 2 , V 3 , V 4 . Para copias u i ∈ V i , v i + 1 ∈ V i + 1 para i = 1 , 2 , 3 , agregue un borde ( u i , v i + 1 ) iff ( 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)$estaba en G. Ahora bien, si nos preguntamos si existe un camino entre cualquiera de los pares para todos u ∈ G, entonces esto exactamente se pregunta si hay un triángulo en G . El gráfico actual tiene 4 n nodos y estamos preguntando acerca de n pares. Sin embargo, podemos agregar 2 n nodos ficticios aislados y tener 3 n consultas en su lugar (agregando una consulta para 2 n pares distintos ( y , d ) donde y ∈ V $(u_1, u_4)$$u\in$$G$$4n$$n$$2n$$3n$$2n$$(y,d)$ y d un maniquí), obteniendo así un 6 n ejemplo -node de exactamente su problema.$y\in V_2\cup V_3$$d$$6n$

La clasificación topológica ( ) luego se trabaja propagando un conjunto de bits de nodos desde el cual se puede alcanzar cada nodo ( O ( m n ) ).$O(m+n)$$O(m n)$

Después del ordenamiento topológico, puede hacer un rechazo rápido de (si el nodo n + x precede al nodo x en el ordenamiento, entonces no hay una ruta de x a 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$

Se pueden agregar otras heurísticas, pero su eficiencia (y la eficiencia de las tres propuestas) depende en gran medida de la estructura del gráfico.