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?1 … n
EDIT: Estou procurando a existência, não caminhos completos.
Respostas:
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.376 n2.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 i ∈ V i , v i + 1 ∈ V i + 1 para i = 1 , 2 , 3 , adicione uma borda ( u i , v i + 1 ) iff ( u , v )V1 V2 V3 V4 vocêEu∈ VEu vi + 1∈ Vi + 1 i = 1 , 2 , 3 ( uEu, 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) u ∈ G 4 n n 2 n 3 n 2 n ( y, d) e d um manequim), obtendo assim umainstância de 6 n- nó exatamente do seu problema.y∈ V2∪ V3 d 6 n
fonte
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 ( m n )
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 + x x x n + x
fonte
Se você deseja manter a memória baixa (evite a matriz ), você pode adicionar algumas heurísticas:O ( N2)
HEURISTIC 3O ( N2) O ( N∗ k ) e > u + N
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.
Outras heurísticas podem ser adicionadas, mas sua eficiência (e eficiência das três propostas) depende muito da estrutura gráfica.
fonte