18
$\begingroup$

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 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, 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 wasn't answered, but it deals with the harder problem of allowing edge insertions interleaved with queries.

This question 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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Related question: cstheory.stackexchange.com/questions/21503/…. $\endgroup$
    – R B
    Commented Jul 20, 2014 at 21:14
  • $\begingroup$ 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! $\endgroup$
    – user4718
    Commented Jul 20, 2014 at 22:53
  • $\begingroup$ 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? $\endgroup$
    – András Salamon
    Commented Jul 25, 2014 at 0:26
  • 7
    $\begingroup$ For theoretical lower bounds, Pǎtrasçu in 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. $\endgroup$
    – András Salamon
    Commented Jul 25, 2014 at 9:26

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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