22-4 Reachability

Let $G = (V, E)$ be a directed graph in which each vertex $u \in V$ is labeled with a unique integer $L(U)$ from the set $\{1, 2, \ldots, |V|\}$. For each vertex $u \in V$, let $R(u) = \{v \in V: u \leadsto v \}$ be the set of vertices that are reachable from $u$. Define $\min(u)$ to be the vertex in $R(u)$ whose label is minimum, i.e., $\min(u)$ is the vertex $v$ such that $L(v) = \min \{L(w): w \in R(u) \}$. Give an $O(V + E)$-time algorithm that computes $\min(u)$ for all vertices $u \in V$.

Compute $G^\text T$ in the usual way, so that $G^\text T$ is $G$ with its edges reversed. Then do a depth-first search on $G^\text T$ , but in the main loop of $\text{DFS}$, consider the vertices in order of increasing values of $L(v)$. If vertex $u$ is in the depth-first tree with root $v$, then $\min(u) = v$. Clearly, this algorithm takes $O(V + E)$ time.

To show correctness, first note that if $u$ is in the depth-first tree rooted at $v$ in $G^\text T$, then there is a path $v \leadsto u$ in $G^\text T$, and so there is a path $u \leadsto v$ in $G$. Thus, the minimum vertex label of all vertices reachable from $u$ is at most $L(v)$, or in other words, $L(v) \ge \min \{L(w): w \in R(u)\}$.

Now suppose that $L(v) > \min \{L(w): w \in R(u) \}$, so that there is a vertex $w \in R(u)$ such that $L(w) < L(v)$. At the time $v.d$ that we started the depthfirst search from $v$, we would have already discovered $w$, so that $w.d < v.d$. By the parenthesis theorem, either the intervals $[v.d, v.f]$, and $[w.d, w.f]$ are disjoint and neither $v$ nor $w$ is a descendant of the other, or we have the ordering $w.d < v.d < v.f < w.f$ and $v$ is a descendant of $w$. The latter case cannot occur, since $v$ is a root in the depth-first forest (which means that $v$ cannot be a descendant of any other vertex). In the former case, since $w.d < v.d$, we must have $w.d < w.f < v.d < v.f$. In this case, since $u$ is reachable from $w$ in $G^\text T$ , we would have discovered $u$ by the time $w.f$, so that $u.d < w.f$. Since we discovered $u$ during a search that started at $v$, we have $v.d \le u.d$. Thus, $v.d \le u.d < w.f < v.d$, which is a contradiction. We conclude that no such vertex $w$ can exist.