Rotear a existência entre n pares de nós

8

Dado um gráfico dirigido acíclico com nodos como se pode determinar se existe um caminho entre qualquer um dos seguintes n pares de nós ( 1 n + 1 ) , ... , ( N n + n ) ? Existe um algoritmo simples em (onde m é o número de arestas) fazendo uma pesquisa em cada nó , mas isso pode ser feito melhor?2n(1n+1),,(nn+n)1 nO(n(n+m))1n

EDIT: Estou procurando a existência, não caminhos completos.

Alexandru
fonte
Não está totalmente claro o que você está perguntando. Você está procurando um único caminho que contenha as bordas mencionadas? Ou você está procurando vários caminhos?
Dave Clarke
2
@ Dave: Ele está procurando o OR de um pequeno pedaço da matriz de fechamento transitivo.
Radu GRIGore
1
@Alexandru, 1-> 4, 2-> 3. Você adiciona 3-> 1, 4-> 2.
Radu GRIGore
6
Você pode calcular o fechamento transitivo através da multiplicação rápida da matriz, que seria melhor que o tempo O (nm) se m for grande.
Chandra Chekuri
4
@alexandru: não foi isso que sua pergunta foi feita, para ser justo. Você estava pedindo um rápido preso, não implementações práticas (que é uma pergunta válida, mas separado)
Suresh Venkat

Respostas:

5

Como Chandra Chekuri apontou em um comentário, você pode apenas calcular o fechamento transitivo através da multiplicação rápida da matriz, resolvendo o problema no tempo O ( ) (use seu método favorito, O ( n 2.376 ) via Coppersmith e Winograd, ou mais praticamente usando O de Strassen ( n 2,81 )), e isso seria bom para gráficos densos.nωn2.376n2.81

Agora, afirmo que, se você puder superar esse tempo de execução para o seu problema em gráficos densos, obteria um algoritmo para detecção de triângulo que é mais eficiente do que computar o produto de duas matrizes booleanas. A existência de um algoritmo desse tipo é um grande problema em aberto.

Vou reduzir o problema do triângulo ao problema de alcançabilidade de n pares de DAG. Suponha que recebamos um gráfico G em nós e queremos determinar se G contém um triângulo.

Agora, a partir de G, crie um DAG G 'da seguinte maneira. Crie quatro cópias do conjunto de vértices, , V 2 , V 3 , V 4 . Para cópias u iV i , v i + 1V i + 1 para i = 1 , 2 , 3 , adicione uma borda ( u i , v i + 1 ) iff ( u , v )V1V2V3V4uiVivi+1Vi+1i=1,2,3(ui,vi+1)(u,v)estava em G. Agora, se perguntar se existe um caminho entre qualquer um dos pares para todo u G, então este seria exatamente estar se perguntando se há um triângulo em G . O gráfico atual possui 4 n nós e estamos perguntando sobre n pares. Entretanto, podemos adicionar 2 n nós fictícios isolados e, em vez disso, ter 3 n consultas (adicionando uma consulta para 2 n pares distintos ( y , d ) em que y V 2(u1,u4)uG4nn2n3n2n(y,d) e d um manequim), obtendo assim umainstância de 6 n- nó exatamente do seu problema.yV2V3d6n

virgi
fonte
0

A classificação topológica ( ) então trabalha abaixo, propagando um conjunto de bits de nós a partir do qual cada nó pode ser alcançado ( O ( m n ) ).O(m+n)O(mn)

Após a classificação topológica, você pode fazer uma rejeição rápida de (se o nó n + x vier antes do nó x na classificação, não haverá caminho de x a n + x ).O(n)n+xxxn+x

Peter Taylor
fonte
Isso realmente não parece ser mais rápido para mim. Se , o algoritmo da pergunta poderia fazer um simples pré-processamento respondendo NÃO se houver um vértice isolado. m=o(n)
Serge Gaspers 09/02
1
Como isso é melhor do que o meu algoritmo básico?
Alexandru
@ Alexandru, acho que é um pouco melhor porque embala os bits. Ou seja, é onde w é a largura da palavra. Não está claro se você deseja essas melhorias. O((m+n)n/W)W
Radu GRIGore
É uma troca: você usa memória extra O (n * n / w) em vez de O (n).
Alexandru
@Alexandru, assintoticamente, na pior das hipóteses, é o mesmo, mas a análise de casos médios é complicada e qual é a melhor opção pode depender das estatísticas da estrutura gráfica esperada.
Peter Taylor
0

Se você deseja manter a memória baixa (evite a matriz ), você pode adicionar algumas heurísticas:O(N2)

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

HEURISTIC 3
Em vez de usar uma matriz de tamanho , é possível usar um buffer (matriz simples ou tabela de hash) das verificações k-anteriores (tamanho O ( N k ) ) que contém um nó e > u + N (u é o nó atual no loop principal) e, durante a primeira verificação geral, se atingirmos um nó contido em um caminho em buffer anterior.O(N2)O(Nk)e>você+N

Outras heurísticas podem ser adicionadas, mas sua eficiência (e eficiência das três propostas) depende muito da estrutura gráfica.

Marzio De Biasi
fonte