Computando um oráculo de existência transitiva de conclusão / caminho

Houve algumas perguntas ( 1 , 2 , 3 ) sobre a conclusão transitiva aqui que me fizeram pensar se algo como isso é possível:

Suponha que obtemos um gráfico direcionado para entrada e gostaríamos de responder a perguntas do tipo " ?", Ou seja, perguntando se existe uma aresta entre dois vértices na conclusão transitiva de um gráfico ? (equivalentemente, "existe um caminho de para em ?").$G$$(u,v)\in G^+$$G$$u$$v$$G$

Suponha que, após determinado você tenha permissão para executar o pré-processamento no tempo e, em seguida, seja necessário responder às consultas no tempo .$G$$f(n,m)$$g(n,m)$

Obviamente, se (ou seja, nenhum pré-processamento é permitido), o melhor que você pode fazer é responder a uma consulta no tempo . (execute o DFS de para retorne true se houver um caminho).$f=0$$g(n)=\Omega(n+m)$$u$$v$

Outro resultado trivial é que, se , você pode calcular o fechamento transitivo e responder às perguntas em .$f=\Omega(min\{n\cdot m,n^\omega\})$$O(1)$

E algo no meio? Se você tiver permissão, digamos tempo de pré-processamento, você pode responder a consultas mais rapidamente que ? Talvez melhorá-lo para ?$f=n^2$$O(m+n)$$O(n)$

Outra variação é: suponha que você tenha tempo de pré-processamento , mas apenas espaço, você pode usar o pré-processamento para responder a consultas mais eficientes que ?$poly(n,m)$$o(n^2)$$O(n+m)$

Podemos dizer algo em geral sobre a troca que permite responder a essas perguntas?$f,g$

Uma estrutura de troca um tanto semelhante é considerada nos sistemas GPS, onde a manutenção de uma tabela de roteamento completa de todas as distâncias entre pares é inviável; portanto, é possível usar a idéia de oráculos de distância que armazenam uma tabela parcial, mas permitem uma aceleração significativa da consulta ao calcular a distância do todo gráfico (geralmente produzindo apenas uma distância aproximada entre pontos).

Existem oráculos de acessibilidade compactos para gráficos planares,

Mikkel Thorup: Oráculos compactos para acessibilidade e distâncias aproximadas em dígrafos planares . J. ACM 51 (6): 993-1024 (2004)

mas são "difíceis" para gráficos gerais (mesmo gráficos esparsos)

Mihai Patrascu: Unificando a paisagem dos limites inferiores da sonda celular . SIAM J. Comput. 40 (3): 827-847 (2011)

No entanto, existe um algoritmo que pode calcular uma rotulagem de alcançabilidade quase ideal

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Consultas sobre acessibilidade e distância através de etiquetas de 2 hop . SIAM J. Comput. 32 (5): 1338-1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algoritmos para otimização de etiquetas de cubos . ICALP 2013: 69-80

Com base no trabalho de Cohen et al. e outros, há bastante pesquisa aplicada (comunidade de banco de dados), veja, por exemplo

Ruoming Jin, Guan Wang: Oracle de acessibilidade simples, rápida e escalável . PVLDB 6 (14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: consultas de acessibilidade rápidas e escaláveis ​​em gráficos por meio de etiquetas podadas com pontos de referência e caminhos . CIKM 2013: 1601-1606

Responderei parcialmente à sua pergunta: parece haver algumas razões pelas quais essa construção pode ser difícil de obter.

Suponha que, dado qualquer gráfico direcionado à borda m de n nós, você possa pré-processá-lo em tempo T (m, n), para que as consultas de acessibilidade possam ser respondidas em tempo q (m, n). Então, por exemplo, você pode encontrar um triângulo em um gráfico de arestas de n nós em . Logo, T ( m , n ) = O ( n 2 ) e q ( $T(O(m),O(n))+n q(O(m),O(n))$$T(m,n)=O(n^2)$ implicaria um resultado inovador. O melhor algoritmo que temos para encontrar triângulos é executado no tempo O ( n ω ) e não está claro se ω = 2 .$q(m,n)=O(n)$$O(n^\omega)$$\omega=2$

Para ver a redução, suponha que queremos encontrar um triângulo em algum grafo . Construir um gráfico 4-camadas em 4 conjuntos de n nós, cada X , Y , Z , W , onde cada nó original v em L tem cópias v X , v Y , v Z , v W . Agora, para cada aresta ( u , v ) em G, adicione as arestas direcionadas ( u X , v Y ) , $G$$n$$X,Y,Z,W$$v$$G$$v_X,v_Y,v_Z,v_W$$(u,v)$$G$ . Isso completa o gráfico. Agora, faça o pré-processamento no tempo T ( O ( m ) , O ( n ) ) e faça as perguntas sobre v X , v W para cada v .$(u_X,v_Y),(u_Y,v_Z),(u_Z,v_W)$$T(O(m),O(n))$$v_X,v_W$$v$

$n^{2+o(1)}$