<p>Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, and subsequently allows for "near-constant time" responses to reachability queries.</p>

<p>Question: Is there a state-of-the-art data structure that has the following features:
(1). Pre-processing time or time to build data structure is linear in number of edges or vertices. This can also be quadratic, as its a once-off process.
(2). Has linear space complexity
(3). Can answer reachability queries in O(1) time (or even logarithmic time)?</p>

<p>The paper I found which mentioned some structures --> <a href="http://www.vldb.org/pvldb/vol7/p1191-wei.pdf" rel="nofollow noreferrer">http://www.vldb.org/pvldb/vol7/p1191-wei.pdf</a> </p>

<p>The trade-off between properties (1)-(3), would be that we want to optimize (3), then (2) to the best possible, while (1) is still important but can be rated lowest. So, optimize (3) > (2) > (1).</p>

<p>The worst case would be to do a BFS/DFS for every single query. The other extreme is to pre-compute reachability for every pair of vertices, but then storage would be O(n^2) in a matrix.</p>

CC BY-SA 3.0
2016-12-01T17:56:26.153Z
Hoping for something better than DFS/BFS?
Sasho Nikolov
CC BY-SA 3.0
2016-12-02T04:51:14.433Z
@SashoNikolov: Yes, I just edited my question with the paper I came across during my search, but I am not sure if this is really the state-of-the-art or are there better ones around. Was hoping for some graph theory guys to help out really.
user43464
CC BY-SA 3.0
2016-12-02T15:52:08.853Z
Your question is unclear. If you only need to solve a single reachability query, I don't believe you can hope for anything better than running DFS. The paper you have linked solves the static data structure problem in which you want to pre-process the graph (possibly taking longer time than DFS) into a small-space data structure so that any reachability query can be answered fast. That can help if you want to solve multiple reachability queries, so that it makes sense to spend some time pre-processing.
Sasho Nikolov
CC BY-SA 3.0
2016-12-03T08:07:11.377Z
Yes, that is exactly what I need. I need a small-space structure that can later answer multiple reachability queries very fast.
user43464
CC BY-SA 3.0
2016-12-03T09:31:32.747Z
Interesting topic.  However, "what is the best one?" is not an answerable question, because what is best depends on your criteria / requirements / workload.  Can you try rephrasing your question?  What exactly are you trying to optimize for?  There are probably many possible algorithms with non-trivial tradeoffs between preprocessing time, space, and per-query time, so you'll need to give us some idea how you plan to evaluate answers and how we should trade those off.
D.W.
CC BY-SA 3.0
2016-12-03T11:46:05.383Z
@cbro: please edit your question so that it asks what you are actually looking for, as per your comment.
András Salamon
<cc.complexity-theory><graph-algorithms><ds.data-structures>
Reachability on DAG (best-known algorithm)
user43464
# Reachability on DAG (best-known algorithm)

(Asked by: username_0 on 2016-12-01)

Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, and subsequently allows for "near-constant time" responses to reachability queries.

Question: Is there a state-of-the-art data structure that has the following features:
(1). Pre-processing time or time to build data structure is linear in number of edges or vertices. This can also be quadratic, as its a once-off process.
(2). Has linear space complexity
(3). Can answer reachability queries in O(1) time (or even logarithmic time)?

The paper I found which mentioned some structures --> <http://www.vldb.org/pvldb/vol7/p1191-wei.pdf>

The trade-off between properties (1)-(3), would be that we want to optimize (3), then (2) to the best possible, while (1) is still important but can be rated lowest. So, optimize (3) > (2) > (1).

The worst case would be to do a BFS/DFS for every single query. The other extreme is to pre-compute reachability for every pair of vertices, but then storage would be O(n^2) in a matrix.

**Tags:** cc.complexity-theory, graph-algorithms, ds.data-structures

> **Comments:**
> **username_1**: Hoping for something better than DFS/BFS?  
> **username_0**: @SashoNikolov: Yes, I just edited my question with the paper I came across during my search, but I am not sure if this is really the state-of-the-art or are there better ones around. Was hoping for some graph theory guys to help out really.  
> **username_1**: Your question is unclear. If you only need to solve a single reachability query, I don't believe you can hope for anything better than running DFS. The paper you have linked solves the static data structure problem in which you want to pre-process the graph (possibly taking longer time than DFS) into a small-space data structure so that any reachability query can be answered fast. That can help if you want to solve multiple reachability queries, so that it makes sense to spend some time pre-processing.  
> **username_0**: Yes, that is exactly what I need. I need a small-space structure that can later answer multiple reachability queries very fast.  
> **username_2**: Interesting topic.  However, "what is the best one?" is not an answerable question, because what is best depends on your criteria / requirements / workload.  Can you try rephrasing your question?  What exactly are you trying to optimize for?  There are probably many possible algorithms with non-trivial tradeoffs between preprocessing time, space, and per-query time, so you'll need to give us some idea how you plan to evaluate answers and how we should trade those off.  
> **username_3**: @cbro: please edit your question so that it asks what you are actually looking for, as per your comment.  

---

## 0 answers

