Cálculo de un oráculo de terminación transitiva / existencia de ruta

Ha habido algunas preguntas ( 1 , 2 , 3 ) sobre la terminación transitiva aquí que me hicieron pensar si algo como esto es posible:

Supongamos que obtenemos un gráfico $G$ entrada dirigido y nos gustaría responder consultas del tipo " ?", Es decir, preguntar si existe un borde entre dos vértices en la terminación transitiva de un gráfico ? (equivalentemente, "¿hay una ruta de a en ?").$(u,v)\in G^+$$G$$u$$v$$G$

Suponga que después de dar se le permite ejecutar el preprocesamiento en el tiempo y luego debe responder consultas en el tiempo .$G$$f(n,m)$$g(n,m)$

Obviamente, si (es decir, no se permite el procesamiento previo), lo mejor que puede hacer es responder una consulta en el tiempo . (ejecute DFS de a y devuelva verdadero si existe una ruta).$f=0$$g(n)=\Omega(n+m)$$u$$v$

Otro resultado trivial es que si , puede calcular el cierre transitivo y luego responder consultas en .$f=\Omega(min\{n\cdot m,n^\omega\})$$O(1)$

¿Qué hay de algo en el medio? Si está permitido, diga tiempo de preprocesamiento, ¿puede responder consultas más rápido que ? Tal vez mejorarlo a ?$f=n^2$$O(m+n)$$O(n)$

Otra variación es: suponga que tiene un tiempo de preprocesamiento , pero solo espacio , ¿puede usar el preprocesamiento para responder consultas más eficientes que ?$poly(n,m)$$o(n^2)$$O(n+m)$

¿Podemos decir algo en general sobre la compensación que permita responder a tales consultas?$f,g$

Se considera una estructura de compensación algo similar en los sistemas GPS, donde no es factible mantener una tabla de enrutamiento completa de todas las distancias por pares entre ubicaciones, por lo que está utilizando la idea de oráculos de distancia que almacena una tabla parcial pero permite una aceleración de consulta significativa al calcular la distancia del conjunto gráfico (generalmente solo produce una distancia aproximada entre puntos).

Existen oráculos de accesibilidad compacta para gráficos planos,

Mikkel Thorup: oráculos compactos para alcanzar y distancias aproximadas en dígrafos planos . J. ACM 51 (6): 993-1024 (2004)

pero son "difíciles" para gráficos generales (incluso gráficos dispersos)

Mihai Patrascu: Unificando el paisaje de los límites inferiores de la sonda celular . SIAM J. Comput. 40 (3): 827-847 (2011)

Sin embargo, existe un algoritmo que puede calcular un etiquetado de accesibilidad cercano al óptimo

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Consultas de alcance y distancia a través de etiquetas de 2 saltos . SIAM J. Comput. 32 (5): 1338-1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algorithms for Hub Label Optimization . ICALP 2013: 69-80

Sobre la base del trabajo de Cohen et al. y otros, hay bastante investigación aplicada (comunidad de bases de datos), ver por ejemplo

Ruoming Jin, Guan Wang: Oracle de accesibilidad simple, rápida y escalable . PVLDB 6 (14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: consultas de accesibilidad rápidas y escalables en gráficos mediante etiquetas podadas con puntos de referencia y caminos . CIKM 2013: 1601-1606

Contestaré su pregunta parcialmente: parece haber algunas razones por las cuales tal construcción puede ser difícil de obtener.

$T(O(m),O(n))+n q(O(m),O(n))$$T(m,n)=O(n^2)$$q(m,n)=O(n)$$O(n^\omega)$$\omega=2$

$G$$n$$X,Y,Z,W$$v$$G$$v_X,v_Y,v_Z,v_W$$(u,v)$$G$$(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)}$