Hopcroft-Tarjan

Abstract view

Algorithmic problem: Biconnected components

Type of algorithm: two steps.

Step 1

Abstract view:

1. A start node [math]\displaystyle{ s }[/math] and an edge [math]\displaystyle{ \{s,v\} }[/math] to an arbitrarily chosen node [math]\displaystyle{ v\in V }[/math] are added to [math]\displaystyle{ G }[/math].
2. The core algorithm is a variation of DFS, where for each node [math]\displaystyle{ v\in V }[/math] two additional nonnegative integral numbers are computed:
   1. The depth of [math]\displaystyle{ v }[/math] in the arborescence created by the DFS procedure.
   2. The lowpoint, that is, the minimal depth of any node [math]\displaystyle{ w\in V }[/math] such that [math]\displaystyle{ (u,w)\in A }[/math] for some immediate or non-immediate successor [math]\displaystyle{ u }[/math] of [math]\displaystyle{ v }[/math] in the DFS tree.
3. The start node [math]\displaystyle{ s }[/math] and the edge [math]\displaystyle{ \{s,v\} }[/math] are removed from [math]\displaystyle{ G }[/math] and from the DFS arborescence (which is rooted at [math]\displaystyle{ v }[/math] afterwards).

Implementation of step 1:

1. Depth: The DFS maintains a global integral number, the current depth. Whenever a node is seen for the first time, its depth attribute is set identical to the current depth. In each forward step, the current depth is increased by one, in each backward step, it is decreased by one.
2. Lowpoint:
   1. Whenever a node [math]\displaystyle{ v\in V }[/math] is seen for the first time, its lowpoint is set identical to its depth.
   2. Whenever an arc [math]\displaystyle{ (v,w) }[/math] is examined such that [math]\displaystyle{ w }[/math] has already been seen and the depth of [math]\displaystyle{ w }[/math] is smaller than the lowpoint of [math]\displaystyle{ v }[/math], the lowpoint of [math]\displaystyle{ v }[/math] is set identical to the depth of [math]\displaystyle{ w }[/math].
   3. In each backward step of DFS from a node [math]\displaystyle{ w }[/math] back to its immediate predecessor [math]\displaystyle{ v }[/math]: If the lowpoint value of [math]\displaystyle{ w }[/math] is smaller than the lowpoint value of [math]\displaystyle{ v }[/math], the lowpoint value of [math]\displaystyle{ v }[/math] is set identical to the lowpoint value of [math]\displaystyle{ w }[/math].

Remarks:

1. We do not choose a start node from the given nodes but insert a new start node to avoid a special treatment of the start node.
2. This is another example where it makes perfect sense to implement graph traversal algorithms as iterators (cf. here). In fact, then the operations on the depth and lowpoint attributes can be inserted in the DFS loop in an easy, obvious way.

Step 2

Definition: A node [math]\displaystyle{ v\in V }[/math] is essential if, for at least one arc [math]\displaystyle{ (v,w) }[/math] in the arborescence from step 1, the lowpoint value of [math]\displaystyle{ w }[/math] is equal to or larger than the depth of [math]\displaystyle{ v }[/math].

Abstract view: A repeated application of DFS, where the start nodes of the individual DFS runs are the essential nodes. In that, the essential nodes are considered in ascending order of their finishing times as computed in step 1. The nodes hit in one DFS run are removed from [math]\displaystyle{ G }[/math] before the next DFS run commences. The node sets visited in the individual DFS runs are returned as the biconnected components.

Correctness

Obviously, the depth and the lowpoint are set correctly according to their intended semantics.

First consider an essential node [math]\displaystyle{ v\in V }[/math]. Let [math]\displaystyle{ (v,w) }[/math] be an arc in the arborescence such that the lowpoint value of [math]\displaystyle{ w }[/math] is equal to or larger than the depth of [math]\displaystyle{ v }[/math]. We have to show that the subarborescence rooted at [math]\displaystyle{ (v,w) }[/math] is connected to the rest of the graph via [math]\displaystyle{ v }[/math] only. So suppose for a contradiction that there is an edge [math]\displaystyle{ \{x,y\} }[/math] such that [math]\displaystyle{ x }[/math] belongs to that subarborescence and [math]\displaystyle{ y }[/math] does not. Then [math]\displaystyle{ y }[/math] must have been seen before [math]\displaystyle{ x }[/math], because otherwise, [math]\displaystyle{ y }[/math] would be in the subarborescence rooted at [math]\displaystyle{ x }[/math]. Since the lowpoint of [math]\displaystyle{ x }[/math] is equal to or larger than the depth of [math]\displaystyle{ v }[/math], [math]\displaystyle{ y }[/math] cannot be a predecessor of [math]\displaystyle{ v }[/math] in the arborescence. Hence, [math]\displaystyle{ y }[/math] was even finished before [math]\displaystyle{ v }[/math] was seen. In particular, [math]\displaystyle{ y }[/math] was finished before [math]\displaystyle{ x }[/math] was seen, which is impossible.

Now consider a node [math]\displaystyle{ v\in V }[/math] that is not essential. Opposite to the first case, we have to show that the subarborescence rooted at an arc [math]\displaystyle{ (v,w) }[/math] is not only connected to the rest of the graph via [math]\displaystyle{ v }[/math]. However, this follows immediately from the definition of the lowpoint value: There is some [math]\displaystyle{ x\in V }[/math] in the subarborescence rooted at [math]\displaystyle{ (v,w) }[/math] connected to some node [math]\displaystyle{ y }[/math] that cannot be in the subarborescence due to its smaller depth.

Complexity

Statement: The asymptotic complexity is linear.

Proof: Follows immediately from the linear asymptotic complexity of DFS.