Computing a transitive completion / path existence oracle

Question

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).

Answer 1

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

Answer 2

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.