What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $O(n\log n)$ which supports $O(1)$ query time for planar graphs. Do trees have better complexity?
1 Answer
$\begingroup$
$\endgroup$
Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the input is a star graph, then you need to know the orientation of every one of the $n-1$ edges).
[1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar reachability in linear space and constant time." 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015.
