Reachability on DAG (best-known algorithm)

Question

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.

Answer 1

[Rooted trees with edges directed away from the root] are DAGs,
and from reachability on such a DAG, one can recover

the root as the unique vertex from which every other vertex is reachable
and
the tree by observing that x is adjacent to y if and only if [x≠y and [one of {x,y} is
reachable from the other of {x,y}] and [there is no vertex z such that [[z is not in {x,y}] and
[[x is reachable from z is reachable from y] or [y is reachable from z is reachable from x]]]]]

.


Thus, by this formula, there are ​ $n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(\hspace{-0.02 in}n^{n-2}\right)$ ​ distinct reachability oracles
for [rooted trees with edges directed away from the root].
$\log_2\hspace{-0.06 in}\left(n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(n^{n-2}\right)\hspace{-0.03 in}\right) \;\; = \;\; \log_2\hspace{-0.06 in}\left(\hspace{-0.02 in}n^{n-1}\right) \;\; = \;\; (n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n) \;\;$,
so any encoding of [reachability oracles for rooted trees with edges directed away from the root]
will need to use more than $\;\;\; \left((n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n)\right)-3 \;\;\;$ bits for more than 3/4 of such DAGs.

By this paper,
"has n^1+o(1) space complexity" ​ and ​ "Can answer reachability queries in O(1) time"
are incompatible:

As described at the bottom of page 5 and the top of page 6,
"butterfly graph"s are directed acyclic.
Accordingly, all of their subgraphs are also DAGs.
By Theorem 1.2 and the two sentences after that,
for constant time, ​ ​ ​ "the space needs to be ​ $n^{1+\Omega \hspace{.02 in}(1)}$ ."

(I'm not aware of any positive results.)