Strong Components in Linear Time Continued

Tarjan’s algorithm

An earlier but considerably more subtle linear-time algorithm to compute strong components was published by Bob Tarjan in 1972. Intuitively, Tarjan’s algorithm identifies a source component of $G$, “deletes” it, and then “recursively” finds the remaining strong components; however, the entire computation happens during a single depth-first search.

Characterizing sink components in a directed graph

Fix an arbitrary depth-first traversal of some directed graph $G$. For each vertex $v$, let $low(v)$ denote the smallest starting time among all vertices reachable from $v$ by a path of tree edges followed by, at most, one non-tree edge. Trivially, $low(v) ≤ v.pre$, because $v$ can reach itself through zero tree edges followed by zero non-tree edges. Tarjan observed that sink components could be characterized in terms of this low function.

Lemma: A vertex $v$ is the root of a sink component of $G$ if and only if $low(v) = v.pre$ and $low(w) < w.pre$ for every proper descendant $w$ of $v$.

Proof: First, let $v$ be a vertex such that $low(v) = v.pre$. Then there is no edge $w\rightarrow x,$ where $w$ is a descendant of $v$ and $x.pre < v.pre$. On the other hand, $v$ cannot reach any vertex $y$ such that $y.pre > v.post$. It follows that $v$ can reach only its descendants, and therefore any descendant of $v$ can reach only descendants of $v$. In particular, $v$ cannot reach its parent (if it has one), so $v$ is the root of its strong component.

Now suppose in addition that $low(w) < w.pre$ for every descendant $w$ of $v$. Then each descendant $w$ can reach another vertex $x$ (which must be another descendant of $v$) such that $x.pre < w.pre$. Thus, by induction, every descendant of $v$ can reach $v$. It follows that the descendants of $v$ comprise the strong component $C$ whose root is $v$. Moreover, $C$ must be a sink component because $v$ cannot reach any vertex outside of $C$.

On the other hand, suppose $v$ is the root of a sink component $C$. Then $v$ can reach another vertex $w$ if and only if $w ∈ C$. But $v$ can reach all of its descendants, and every vertex in $C$ is a descendant of $v$, so $v’s$ descendants comprise $C$. If $low(w) = w.pre$ for any other node $w ∈ C$, then $w$ would be another root of $C$, which is impossible.

Computing $low(v)$ for every vertex $v$ via depth-first search is straightforward; see the algorithm below.

The lemma above implies that after running $FindLow$, we can identify the root of every sink component in $O(V + E)$ time (by a global whatever-first search) and then mark and delete those sink components in $O(V + E)$ additional time (by calling whatever-first search at each root) and then recurse. Unfortunately, the resulting algorithm might require $V$ iterations, each removing only a single vertex, thus naively giving us a total running time of $O(V E)$.