<p>See "interval labeling" and "2-hop labeling" which are apparently quite efficient in practice, both in time and space, and may give you what you want. In general there's quite a bunch of "reachability indexing" schemes for DAGs.</p>

CC BY-SA 3.0
2014-09-14T16:45:10.280Z
2014-09-14T16:45:10.280Z
jkff
<p><strong>For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time?  Ideally I seek an algorithm using only O(log n) space per vertex and logarithmic time</strong> where $n=|V|+|E|$.</p>

<p>It seemed intuitively obvious to me that a data structure like this ought to exist, based on some generalization of standard sorting algorithms.  But I was surprised that I couldn't find any.  Everything I came across either made assumptions about the graph (e.g. planarity) or solved a harder problem in quadratic time/space (e.g. queries interleaved with graph modifications).</p>

<p>The <a href="https://en.wikipedia.org/wiki/Reachability" rel="noreferrer">Wikipedia page on Reachability</a> only covers one general algorithm (Floyd-Warshall); the rest of the page deals with special cases involving assumptions like the graph being planar (it isn't).</p>

<p>The most commonly cited paper in this space appears to be <a href="http://dx.doi.org/10.1016/0304-3975(86)90098-8" rel="noreferrer" title="Amortized efficiency of a path retrieval data structure">Amortized efficiency of a path retrieval data structure</a>, but this and all the papers it cites involve either O(n^2) space or else O(n^2) time in order to allow updates to the graph interleaved with the queries (i.e. no preprocessing).</p>

<p><a href="https://cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability">This question</a> wasn't answered, but it deals with the harder problem of allowing edge insertions interleaved with queries.</p>

<p><a href="https://cstheory.stackexchange.com/questions/8503/what-persistent-data-structure-for-a-set-of-partially-ordered-elements">This question</a> asked for a persistent (pure functional) data structure, which isn't required here.  The "Succinct Posets" paper needs $O(n^2)$ space but it achieves $O(1)$-time queries; I seek a worse-time, better-space algorithm.</p>

<p>Mostly looking for a foothold in the literature here.  If there's a survey paper on graph reachability that doesn't spend 99% of its time on the planar-graph case, that would help.</p>

CC BY-SA 3.0
2014-07-20T21:14:25.010Z
Related question: http://cstheory.stackexchange.com/questions/21503/computing-a-transitive-completion-path-existance-oracle.
R B
CC BY-SA 3.0
2014-07-20T22:53:08.533Z
Thanks for the link R.B..  That question and the first answer don't deal with space (except a brief mention of a quadratic-space bound, which is what this question seeks an improvement upon).  The second answer alludes to a negative result for distance queries (i.e. integer-valued or real-valued) rather than reachability (i.e. {0,1}-valued) which are an easier problem.  Thanks, though!
user4718
CC BY-SA 3.0
2014-07-25T00:26:52.447Z
Shortcut routing, or the references mentioned by Christian Sommer at the related question, might work in practice.  Are you looking for a practical approach or theoretical lower bounds?
András Salamon
CC BY-SA 3.0
2014-07-25T09:26:02.097Z
For theoretical lower bounds, Pǎtrasçu in http://dx.doi.org/10.1137/09075336X commented "The following problem appears very hard: preprocess a sparse directed graph in less than $n^2$ space, such that reachability queries (can $u$ be reached from $v$?) are answered efficiently.  The problem seems to belong to folklore, and we are not aware of any nontrivial positive results."  He went on to prove a lower bound that allows your parameters, but remarked "Note, however, that our lower bound is still very far from the conjectured hardness of the problem."  So the answer seems to be: probably no.
András Salamon
<graph-algorithms>
DAG reachability with O(n log n) space and O(log n)-time queries?
user4718
# DAG reachability with O(n log n) space and O(log n)-time queries?

(Asked by: username_0 on 2014-07-20)

**For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time? Ideally I seek an algorithm using only O(log n) space per vertex and logarithmic time** where $n=|V|+|E|$.

It seemed intuitively obvious to me that a data structure like this ought to exist, based on some generalization of standard sorting algorithms. But I was surprised that I couldn't find any. Everything I came across either made assumptions about the graph (e.g. planarity) or solved a harder problem in quadratic time/space (e.g. queries interleaved with graph modifications).

The [Wikipedia page on Reachability](https://en.wikipedia.org/wiki/Reachability) only covers one general algorithm (Floyd-Warshall); the rest of the page deals with special cases involving assumptions like the graph being planar (it isn't).

The most commonly cited paper in this space appears to be [Amortized efficiency of a path retrieval data structure](http://dx.doi.org/10.1016/0304-3975(86)90098-8 "Amortized efficiency of a path retrieval data structure"), but this and all the papers it cites involve either O(n^2) space or else O(n^2) time in order to allow updates to the graph interleaved with the queries (i.e. no preprocessing).

[This question](https://cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability) wasn't answered, but it deals with the harder problem of allowing edge insertions interleaved with queries.

[This question](https://cstheory.stackexchange.com/questions/8503/what-persistent-data-structure-for-a-set-of-partially-ordered-elements) asked for a persistent (pure functional) data structure, which isn't required here. The "Succinct Posets" paper needs $O(n^2)$ space but it achieves $O(1)$-time queries; I seek a worse-time, better-space algorithm.

Mostly looking for a foothold in the literature here. If there's a survey paper on graph reachability that doesn't spend 99% of its time on the planar-graph case, that would help.

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: Related question: http://cstheory.stackexchange.com/questions/21503/computing-a-transitive-completion-path-existance-oracle.  
> **username_0**: Thanks for the link R.B..  That question and the first answer don't deal with space (except a brief mention of a quadratic-space bound, which is what this question seeks an improvement upon).  The second answer alludes to a negative result for distance queries (i.e. integer-valued or real-valued) rather than reachability (i.e. {0,1}-valued) which are an easier problem.  Thanks, though!  
> **username_2**: Shortcut routing, or the references mentioned by Christian Sommer at the related question, might work in practice.  Are you looking for a practical approach or theoretical lower bounds?  
> **username_2**: For theoretical lower bounds, Pǎtrasçu in http://dx.doi.org/10.1137/09075336X commented "The following problem appears very hard: preprocess a sparse directed graph in less than $n^2$ space, such that reachability queries (can $u$ be reached from $v$?) are answered efficiently.  The problem seems to belong to folklore, and we are not aware of any nontrivial positive results."  He went on to prove a lower bound that allows your parameters, but remarked "Note, however, that our lower bound is still very far from the conjectured hardness of the problem."  So the answer seems to be: probably no.  

---

## 1 answers

### Answer by username_3 on 2014-09-14. Score: 3

See "interval labeling" and "2-hop labeling" which are apparently quite efficient in practice, both in time and space, and may give you what you want. In general there's quite a bunch of "reachability indexing" schemes for DAGs.


---

