Hopcroft-Tarjan

Abstract view

Algorithmic problem: Biconnected components

Type of algorithm: two steps.

Step 1

Abstract view: 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 of [math]\displaystyle{ v }[/math] in the DFS tree.

Implementation:

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{ w }[/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 valueof [math]\displaystyle{ w }[/math] is smaller than the lowpoint value of [math]\displaystyle{ v }[/math], the set the latter value identical to the former value.

Remark: This is another example where it makes perfect sense to implement graph traversal algorithms as iterators. In fact, then the operations on the depth and lowpoint attributes can be inserted in the DFS loop in an easy, obvious way (cf. here).

Step 2

Definition: A node [math]\displaystyle{ v\in V }[/math] is essential if, for each 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{ w }[/math].

Abstract view: A repeated application of DFS, where the start nodes of the individual DFS runs are the essential node. 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.

For a biconnected component [math]\displaystyle{ C }[/math], let [math]\displaystyle{ (v,w) }[/math] denote the first arc in the subgraph induced by [math]\displaystyle{ C }[/math] that is considered by the DFS in step 1.

In the following, the root of a biconnected component [math]\displaystyle{ C }[/math] is the first node of [math]\displaystyle{ C }[/math] seen in the DFS in step 1. We say that the root [math]\displaystyle{ v_1 }[/math] of some biconnected component [math]\displaystyle{ C_1 }[/math] follows the root [math]\displaystyle{ v_2 }[/math] of some biconnected component [math]\displaystyle{ C_2 }[/math] if [math]\displaystyle{ v_1\neq v_2 }[/math] and both nodes were on the DFS path in step 1 at some stage such that [math]\displaystyle{ v_2 }[/math] preceded [math]\displaystyle{ v_1 }[/math] on this path. The subarborecence

Obviously, the biconnected component [math]\displaystyle{ C }[/math] is exactly the following node set: all nodes in the subarborescence rooted at the root [math]\displaystyle{ v }[/math] of a biconnected component minus all nodes in all subarborescences whose roots

We have to show that the nodes whose lowpoints are not smaller than their depths are exactly the roots of biconnected components in the arborescence created in step 1.

First consider a node [math]\displaystyle{ v\in V }[/math] whose lowpoint is smaller than its depth. Then [math]\displaystyle{ v }[/math] cannot be

Complexity

Statement: The asymptotic complexity is linear.

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