Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we can get $O(1)$ reachability queries between any two special nodes $v_i$ and $v_j$?

For $n = V$, this is just the usual reachability problem. I want to focus on the case where $n \ll V$. Using $n$ depth-first searches starting at the special vertices, it is straightforward to obtain an $O(nE)$-time algorithm. Can this be beaten? What if we relax to $O(\log n)$, $O(n)$, or $O(\log V)$ query time?

EDIT (May 3, 2011). One comment points out that bounds like $O(nE/V^\alpha)$, $\alpha > 0$ imply sub-cubic matrix multiplication bounds. On the other hand, a bound like $O(\max(n^2 V, E))$ for the restricted reachability problem would not imply a sub-cubic method, yet would still be quite useful for $n \ll E / V$.

  • 2
    $\begingroup$ one small note: Let's say I even allow you query time O($V^{0.36}$). Then if you can find an O($nE / V^{0.63}$) time preprocessing algorithm, I can convert it to a new faster algorithm for matrix multiplication. So if you are a pessimist, then you can't expect a much faster preprocessing time than a possible $V^{0.63}$ factor improvement over the trivial O($nE$) algorithm. $\endgroup$
    – virgi
    Apr 10, 2011 at 2:57
  • 1
    $\begingroup$ What matters more is the space you can use for preprocess. This is a case in Patrascu's paper that when $|V| = n \log n$, for $n\log^{O(1)} n$ space, there is an $\Omega(\log n/ \log \log n)$ lower bound. $\endgroup$
    – Wei Yu
    Apr 10, 2011 at 7:44


Your Answer

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