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

1. Compute the component graph $G^{\text{SCC}}$ (in order to remove simple cycles from graph $G$), and label each vertex in $G^{\text{SCC}}$ with the smallest label of vertex in that $G^{\text{SCC}}$. Following chapter 22.5 the time complexity of this procedure is $O(V + E)$.

2. On $G^{\text{SCC}}$, execute the below algorithm. Notice that if we memorize this function it will be invoked at most $V + E$ times. Its time complexity is also $O(V + E)$.

REACHABILITY(u)
    u.min = u.label
    for each v ∈ Adj[u]
        u.min = min(u.min, REACHABILITY(v))
    return u.min

3. Back to graph $G$, the value of $\min(u)$ on Graph $G$ is the value of $\min(u.scc)$ on Graph $G^{\text{SCC}}$.

Alternate solution: Transpose the graph. Call $\text{DFS}$, but in the main loop of $\text{DFS}$, consider the vertices in order of their labels. In the $\text{DFS-VISIT}$ subroutine, upon discovering a new node, we set its $\text{min}$ to be the label of its root.