# Computing a transitive completion / path existence oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible:

Assume we get an input directed graph $$G$$ and would like to answer queries of type "$$(u,v)\in G^+$$?", i.e. asking if there exists an edge between two vertices in the transitive completion of a graph $$G$$? (equivalently, "is there a path from $$u$$ to $$v$$ in $$G$$?").

Assume after given $$G$$ you are allowed to run preprocessing in time $$f(n,m)$$ and then required to answer queries in time $$g(n,m)$$.

Obviously, if $$f=0$$ (i.e. no preprocessing is allowed), the best you can do is answer a query in time $$g(n)=\Omega(n+m)$$. (run DFS from $$u$$ to $$v$$ and return true if there exists a path).

Another trivial result is that if $$f=\Omega(min\{n\cdot m,n^\omega\})$$, you can compute the transitive closure and then answer queries in $$O(1)$$.

What about something in the middle? If you are allowed, say $$f=n^2$$ preprocessing time, can you answer queries faster than $$O(m+n)$$? Maybe improve it to $$O(n)$$?

Another variation is: assume you have $$poly(n,m)$$ preprocessing time, but only $$o(n^2)$$ space, can you use the preprocessing to answer queries more efficient than $$O(n+m)$$?

Can we say anything in general about the $$f,g$$ tradeoff that allows answering such queries?

A somewhat similar tradeoff structure is considered in GPS systems, where holding a complete routing table of all pairwise distances between locations is infeasible so it's using the idea of distance oracles which stores a partial table but allow significant query speedup over computing the distance of the whole graph (usually yielding only approximated distance between points).

• Hamming distance between what two nodes $i$ and $j$ can reach in $t$ hops might be a more informative metric. – Chad Brewbaker Mar 12 '14 at 22:16

Compact reachability oracles exist for planar graphs,

Mikkel Thorup: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004)

but are "hard" for general graphs (even sparse graphs)

Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011)

Nevertheless, there is an algorithm that can compute a close-to-optimal reachability labeling

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Reachability and Distance Queries via 2-Hop Labels. 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

Building on the work of Cohen et al. and others, there is quite a bit of applied research (database community) see e.g.

Ruoming Jin, Guan Wang: Simple, Fast, and Scalable Reachability Oracle. PVLDB 6(14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. CIKM 2013: 1601-1606

I'll answer your question partially: there seem to be some reasons why such a construction may be hard to obtain.

Suppose that given any n-node m-edge directed graph you could preprocess it in T(m,n) time so that reachability queries can be answered in q(m,n) time. Then, for instance, you could find a triangle in an n-node m-edge graph in $T(O(m),O(n))+n q(O(m),O(n))$ time. Hence $T(m,n)=O(n^2)$ and $q(m,n)=O(n)$ would imply a breakthrough result. The best algorithm we have for triangle finding runs in $O(n^\omega)$ time and it's unclear whether $\omega=2$.

To see the reduction, suppose we want to find a triangle in some graph $G$. Build a 4-layered graph on 4 sets of $n$ nodes each $X,Y,Z,W$ where each original node $v$ in $G$ has copies $v_X,v_Y,v_Z,v_W$. Now for each edge $(u,v)$ in $G$ add the directed edges $(u_X,v_Y),(u_Y,v_Z),(u_Z,v_W)$. This completes the graph. Now do the preprocessing in $T(O(m),O(n))$ time, and ask the queries about $v_X,v_W$ for each $v$.

Probably with some more work one can change the reduction to also list the triangles in a graph (currently it only lists the nodes in triangles). If one can do this efficiently, then one could probably get some conditional lower bound based on 3SUM requiring $n^{2+o(1)}$ time as well, using a result of Patrascu from 2010.