Biconnected Component

• Biconnected component | Wikipedia
• Definition: In a biconnected graph
  • Either removal of an edge disconnects the graph (a single edge), or
  • Every three vertices in the component are contained in a simple cycle.
• Articulation vertex: an intersection of two different biconnected component. There is only one articulation vertex, otherwise the two components would just be one.
• Bi-connection provides fault tolerance.

Solution

• For vertex $v$, if a child $s$ of $v$ has $\text{Low}(s)\ge \text{DFS}\#(v)$, then $v$ is articulation vertex. (As there could be $s⇝v$, but $v$ has no back edge)

$$\text{Low}(v)=\min \{\begin{array}{l}\text{DFS}\#(v)\\ \text{Low}(s),\text{ for each child }s\\ \text{DFS}\#(w),\text{ where }(v,w)\text{ is a back edge}\end{array}$$

• Low-point is the lowest depth of neighbors and all descendants of $v$ (included) in the DFS tree

counter = 1, mark all vertices as not visited
BICONNECTED-COMOPNENTS(V)
    mark v as visited
    DFS#(v) = counter
    counter += 1
    Low(v) = DFS#(v)
    for each edge (v, w)
        if w not visited
            w.parent = v
            BICONNECTED-COMPONENT(w)
            Low(v) = min( Low(v), Low(w) )
                if Low(w) >= DFS#(v)
                    report v is an articulation vertex
                    subgraph rooted at s and v forms a biconnected graph
        else if w != v.parent
            Low(v) = min( Low(v), DFS#(w) )