9
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.