<p>Compact reachability oracles exist for planar graphs,</p>

<p><em>Mikkel Thorup: <a href="http://dx.doi.org/10.1145/1039488.1039493">Compact oracles for reachability and approximate distances in planar digraphs</a>. J. ACM 51(6): 993-1024 (2004)</em></p>

<p>but are "hard" for general graphs (even sparse graphs)</p>

<p><em>Mihai Patrascu: <a href="http://dx.doi.org/10.1137/09075336X">Unifying the Landscape of Cell-Probe Lower Bounds</a>. SIAM J. Comput. 40(3): 827-847 (2011)</em></p>

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

<p><em>Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: <a href="http://dx.doi.org/10.1137/S0097539702403098">Reachability and Distance Queries via 2-Hop Labels</a>. SIAM J. Comput. 32(5): 1338-1355 (2003)</em></p>

<p><em>Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: <a href="http://dx.doi.org/10.1007/978-3-642-39206-1_7">Algorithms for Hub Label Optimization</a>. ICALP 2013: 69-80</em></p>

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

<p><em>Ruoming Jin, Guan Wang: <a href="http://www.vldb.org/pvldb/vol6/p1978-jin.pdf">Simple, Fast, and Scalable Reachability Oracle</a>. PVLDB 6(14): 1978-1989 (2013)</em></p>

<p><em>Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: <a href="http://dx.doi.org/10.1145/2505515.2505724">Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths</a>. CIKM 2013: 1601-1606</em></p>

CC BY-SA 3.0
2014-07-20T04:56:16.343Z
2014-07-20T05:01:37.963Z
2014-07-20T05:01:37.963Z
Christian Sommer
<p>I'll answer your question partially: there seem to be some reasons why such a construction may be hard to obtain.</p>

<p>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$. </p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-07-19T22:51:06.837Z
2014-07-19T22:51:06.837Z
virgi
<p>There has been a few questions (<a href="https://cstheory.stackexchange.com/questions/21488/deciding-transitivity-of-a-directed-acyclic-graph">1</a>, <a href="https://cstheory.stackexchange.com/questions/21470/transitivity-check-vs-transitive-clousure">2</a>, <a href="https://cstheory.stackexchange.com/questions/4427/approximating-transitive-reduction-of-a-transitive-closure-of-a-dag/21498#21498">3</a>) about transitive completion here that made me think if something like this is possible:</p>
<blockquote>
<p>Assume we get an input directed graph <span class="math-container">$G$</span> and would like to answer queries of type &quot;<span class="math-container">$(u,v)\in G^+$</span>?&quot;, i.e. asking if there exists an edge between two vertices in the transitive completion of a graph <span class="math-container">$G$</span>? (equivalently, &quot;is there a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> in <span class="math-container">$G$</span>?&quot;).</p>
<p>Assume after given <span class="math-container">$G$</span> you are allowed to run preprocessing in time <span class="math-container">$f(n,m)$</span> and then required to answer queries in time <span class="math-container">$g(n,m)$</span>.</p>
</blockquote>
<p>Obviously, if <span class="math-container">$f=0$</span> (i.e. no preprocessing is allowed), the best you can do is answer a query in time <span class="math-container">$g(n)=\Omega(n+m)$</span>. (run DFS from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> and return true if there exists a path).</p>
<p>Another trivial result is that if <span class="math-container">$f=\Omega(min\{n\cdot m,n^\omega\})$</span>, you can compute the transitive closure and then answer queries in <span class="math-container">$O(1)$</span>.</p>
<p>What about something in the middle? If you are allowed, say <span class="math-container">$f=n^2$</span> preprocessing time, can you answer queries faster than <span class="math-container">$O(m+n)$</span>? Maybe improve it to <span class="math-container">$O(n)$</span>?</p>
<p>Another variation is: assume you have <span class="math-container">$poly(n,m)$</span> preprocessing time, but only <span class="math-container">$o(n^2)$</span> space, can you use the preprocessing to answer queries more efficient than <span class="math-container">$O(n+m)$</span>?</p>
<blockquote>
<p>Can we say anything in general about the <span class="math-container">$f,g$</span> tradeoff that allows answering such queries?</p>
</blockquote>
<p>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 <a href="http://download.springer.com/static/pdf/194/art%253A10.1007%252Fs00453-011-9543-0.pdf?auth66=1394799508_d3b2253c4e8abb7060cb04bc05f4e19c&amp;ext=.pdf" rel="noreferrer">distance oracles</a> 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).</p>

CC BY-SA 3.0
2014-03-12T22:16:36.440Z
Hamming distance between what two nodes $i$ and $j$ can reach in $t$ hops might be a more informative metric.
Chad Brewbaker
<graph-theory><graph-algorithms><space-time-tradeoff><transitive-closure>
Computing a transitive completion / path existence oracle
R B
# Computing a transitive completion / path existence oracle

(Asked by: username_0 on 2014-03-12)

There has been a few questions ([1](https://cstheory.stackexchange.com/questions/21488/deciding-transitivity-of-a-directed-acyclic-graph), [2](https://cstheory.stackexchange.com/questions/21470/transitivity-check-vs-transitive-clousure), [3](https://cstheory.stackexchange.com/questions/4427/approximating-transitive-reduction-of-a-transitive-closure-of-a-dag/21498#21498)) 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](http://download.springer.com/static/pdf/194/art%253A10.1007%252Fs00453-011-9543-0.pdf?auth66=1394799508_d3b2253c4e8abb7060cb04bc05f4e19c&ext=.pdf) 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).

**Tags:** graph-theory, graph-algorithms, space-time-tradeoff, transitive-closure
> **Comments:**
> **username_1**: Hamming distance between what two nodes $i$ and $j$ can reach in $t$ hops might be a more informative metric.  

---

## 2 answers

### Answer by username_2 on 2014-07-20. Score: 7 | Accepted answer

Compact reachability oracles exist for planar graphs,

*Mikkel Thorup: [Compact oracles for reachability and approximate distances in planar digraphs](http://dx.doi.org/10.1145/1039488.1039493). 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](http://dx.doi.org/10.1137/09075336X). 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](http://dx.doi.org/10.1137/S0097539702403098). SIAM J. Comput. 32(5): 1338-1355 (2003)*

*Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: [Algorithms for Hub Label Optimization](http://dx.doi.org/10.1007/978-3-642-39206-1_7). 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](http://www.vldb.org/pvldb/vol6/p1978-jin.pdf). 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](http://dx.doi.org/10.1145/2505515.2505724). CIKM 2013: 1601-1606*


---

### Answer by username_3 on 2014-07-19. Score: 4

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.


---

