Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 6

A strongly connected component is a maximal set of vertices that are mutually reachable in a directed graph; a vertex reaches itself by a length-zero path. The condensation graph, also called the SCC graph, contracts each such component to one vertex and retains directed edges between different components. It is a Directed acyclic graph, since a cycle of components would make them mutually reachable and therefore one component.

For an original seven-vertex example, take cycles $a\to b\to c\to a$, $d\to e\to d$, $f\to g\to f$, and add $c\to d$, $e\to f$. The three components are $\{a,b,c\}$, $\{d,e\}$ and $\{f,g\}$. Their condensation is the three-vertex directed chain in that order: there is no return edge from a later component to an earlier one.

Apply the two-pass strongly connected component algorithm:

1. Run depth-first search over all vertices of $G$, recording their finish order.
2. Construct the graph transpose by reversing every edge.
3. Mark every vertex unvisited again. In decreasing first-pass finish order, start a transpose search whenever the next vertex is unvisited. The vertices newly reached by each search form one strongly connected component.

The finish order prevents a second-pass search from entering a different still-unassigned component, while mutual reachability makes it visit the entire current component. With adjacency lists, each traversal and the transposition scan takes $O(|V|+|E|)$ time. Thus the total worst-case time is $\Theta (|V|+|E|)$, including isolated vertices.

Because the vertex set is finite, at least one vertex occurs infinitely often, so $\mathrm{Inf}(\rho )$ is nonempty. Let $u,v$ belong to this set. After any chosen visit to $u$, a later visit to $v$ exists; the intervening edges give a directed walk from $u$ to $v$. After that visit to $v$, a later visit to $u$ also exists, giving a walk in the other direction. Removing repeated portions gives directed paths if desired.

Thus every pair in $\mathrm{Inf}(\rho )$ is mutually reachable and belongs to the same strongly connected component. This proves the claimed inclusion, which need not be equality: an infinite walk can repeatedly follow one cycle while omitting other vertices in its component. This is the recurrence-set part of the infinite walk criterion in a finite directed graph.

An infinite trace exists exactly when a directed cycle is reachable from $s$, by the infinite walk criterion in a finite directed graph. Compute the reachable set with depth-first search, compute its strongly connected components, and return true if any component has at least two vertices or contains a self-loop. A singleton without a self-loop does not qualify.

If the test succeeds, follow a path from $s$ to the cycle and traverse the cycle forever. Conversely, an infinite trace in a finite graph repeats a vertex, producing a reachable nonempty closed walk and hence a directed cycle. Reachability, component construction and the self-loop check all scan adjacency lists only a constant number of times. The worst-case time is $O(|V|+|E|)$, with $O(|V|+|E|)$ auxiliary space for a straightforward transpose-based implementation.