<p>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$?</p>

<p>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?</p>

<p>EDIT (May 3, 2011). One comment points out that bounds like $O(nE/V^\alpha)$, $\alpha &gt; 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$. </p>

CC BY-SA 3.0
2011-04-10T02:57:04.260Z
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.
virgi
CC BY-SA 3.0
2011-04-10T07:44:47.333Z
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.
Wei Yu
<ds.algorithms><graph-algorithms><time-complexity><directed-acyclic-graph><transitive-closure>
Restricted Reachability Problem
Shaun Harker
# Restricted Reachability Problem

(Asked by: username_0 on 2011-04-09)

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$.

**Tags:** ds.algorithms, graph-algorithms, time-complexity, directed-acyclic-graph, transitive-closure
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

