Reachability on DAG (best-known algorithm)
[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 n1+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.)