22-2 Articulation points, bridges, and biconnected components

Let $G = (V, E)$ be a connected, undirected graph. An articulation point of $G$ is a vertex whose removal disconnects $G$. A bridge of $G$ is an edge whose removal disconnects $G$. A biconnected component of $G$ is a maximal set of edges such that any two edges in the set lie on a common simple cycle. Figure 22.10 illustrates these definitions. We can determine articulation points, bridges, and biconnected components using depth-first search. Let $G_\pi = (V, E_\pi)$ be a depth-first tree of $G$.

a. Prove that the root of $G_\pi$ is an articulation point of $G$ if and only if it has at least two children in $G_\pi$.

b. Let $v$ be a nonroot vertex of $G_\pi$. Prove that $v$ is an articulation point of $G$ if and only if $v$ has a child $s$ such that there is no back edge from $s$ or any descendant of $s$ to a proper ancestor of $v$.

c. Let

$$v.low = \min \begin{cases} v.d, \\ w.d:(u,w) \text{ is a back edge for some descendant } u \text{ of } v. \end{cases}$$

Show how to computer $v.low$ for all vertices $v \in V$ in $O(E)$ time.

d. Show how to compute all articulation points in $O(E)$ time.

e. Prove that an edge of $G$ is a bridge if and only if it does not lie on any simple cycle of $G$.

f. Show how to compute all the bridges of $G$ in $O(E)$ time.

g. Prove that the biconnected components of $G$ partition the nonbridge edges of $G$.

h. Give an $O(E)$-time algorithm to label each edge $e$ of $G$ with a positive integer $e.bcc$ such that $e.bcc = e'.bcc$ if and only if $e$ and $e'$ are in the same biconnected component.

a. First suppose the root $r$ of $G_\pi$ is an articulation point. Then the removal of $r$ from $G$ would cause the graph to disconnect, so $r$ has at least $2$ children in $G$. If $r$ has only one child $v$ in $G_\pi$ then it must be the case that there is a path from $v$ to each of $r$'s other children. Since removing $r$ disconnects the graph, there must exist vertices $u$ and $w$ such that the only paths from $u$ to $w$ contain $r$.

To reach $r$ from $u$, the path must first reach one of $r$'s children. This child is connect to $v$ via a path which doesn't contain $r$.

To reach $w$, the path must also leave $r$ through one of its children, which is also reachable by $v$. This implies that there is a path from $u$ to $w$ which doesn't contain $r$, a contradiction.

Now suppose $r$ has at least two children $u$ and $v$ in $G_\pi$. Then there is no path from $u$ to $v$ in $G$ which doesn't go through $r$, since otherwise $u$ would be an ancestor of $v$. Thus, removing $r$ disconnects the component containing $u$ and the component containing $v$, so $r$ is an articulation point.

b. Suppose that $v$ is a nonroot vertex of $G_\pi$ and that $v$ has a child $s$ such that neither $s$ nor any of $s$'s descendants have back edges to a proper ancestor of $v$. Let $r$ be an ancestor of $v$, and remove $v$ from $G$. Since we are in the undirected case, the only edges in the graph are tree edges or back edges, which means that every edge incident with $s$ takes us to a descendant of $s$, and no descendants have back edges, so at no point can we move up the tree by taking edges. Therefore $r$ is unreachable from $s$, so the graph is disconnected and $v$ is an articulation point.

Now suppose that for every child of $v$ there exists a descendant of that child which has a back edge to a proper ancestor of $v$. Remove $v$ from $G$. Every subtree of $v$ is a connected component. Within a given subtree, find the vertex which has a back edge to a proper ancestor of $v$. Since the set $T$ of vertices which aren't descendants of $v$ form a connected component, we have that every subtree of $v$ is connected to $T$. Thus, the graph remains connected after the deletion of $v$ so $v$ is not an articulation point.

c. Since $v$ is discovered before all of its descendants, the only back edges which could affect $v.low$ are ones which go from a descendant of $v$ to a proper ancestor of $v$. If we know $u.low$ for every child $u$ of $v$, then we can compute $v.low$ easily since all the information is coded in its descendants.

Thus, we can write the algorithm recursively: If $v$ is a leaf in $G_\pi$ then $v.low$ is the minimum of $v.d$ and $w.d$ where $(v, w)$ is a back edge. If $v$ is not a leaf, $v$ is the minimum of $v.d$, $w.d$ where $(v, w)$ is a back edge, and $u.low$, where $u$ is a child of $v$. Computing $v.low$ for a vertex is linear in its degree. The sum of the vertices' degrees gives twice the number of edges, so the total runtime is $O(E)$.

d. First apply the algorithm of part (c) in $O(E)$ to compute $v.low$ for all $v \in V$. If $v.low$ = $v.d$ if and only if no descendant of $v$ has a back edge to a proper ancestor of $v$, if and only if $v$ is not an articulation point.

Thus, we need only check $v.low$ versus $v.d$ to decide in constant time whether or not $v$ is an articulation point, so the runtime is $O(E)$.

e. An edge $(u, v)$ lies on a simple cycle if and only if there exists at least one path from $u$ to $v$ which doesn't contain the edge $(u, v)$, if and only if removing $(u, v)$ doesn't disconnect the graph, if and only if $(u, v)$ is not a bridge.

f. A edge $(u, v)$ lies on a simple cycle in an undirected graph if and only if either both of its endpoints are articulation points, or one of its endpoints is an articulation point and the other is a vertex of degree $1$. There's also a special case where there's only one edge whose incident vertices are both degree $1$. We can check this case in constant time. Since we can compute all articulation points in $O(E)$ and we can decide whether or not a vertex has degree $1$ in constant time, we can run the algorithm in part (d) and then decide whether each edge is a bridge in constant time, so we can find all bridges in $O(E)$ time.

g. It is clear that every nonbridge edge is in some biconnected component, so we need to show that if $C_1$ and $C_2$ are distinct biconnected components, then they contain no common edges. Suppose to the contrary that $(u, v)$ is in both $C_1$ and $C_2$.

Let $(a, b)$ be any edge in $C_1$ and $(c, d)$ be any edge in $C_2$.

Then $(a, b)$ lies on a simple cycle with $(u, v)$, consisting of the path

$$a, b, p_1, \ldots, p_k, u, v, p_{k + 1}, \ldots, p_n, a.$$

Similarly, $(c, d)$ lies on a simple cycle with $(u, v)$ consisting of the path

$$c, d, q_1, \ldots, q_m, u, v, q_{m + 1}, \ldots, q_l, c.$$

This means

$$a, b, p_1, \ldots, p_k, u, q_m, \ldots, q_1, d, c, q_l , \ldots, q_{m + 1}, v, p_{k + 1}, \ldots, p_n,$$

is a simple cycle containing $(a, b)$ and $(c, d)$, a contradiction. Thus, the biconnected components form a partition.

h. Locate all bridge edges in $O(E)$ time using the algorithm described in part (f). Remove each bridge from $E$. The biconnected components are now simply the edges in the connected components. Assuming this has been done, run the following algorithm, which clearly runs in $O(|E|)$ where $|E|$ is the number of edges originally in $G$.

VISIT-BCC(G, u, k)
    u.color = GRAY
    for each v ∈ G.Adj[u]
        (u, v).bcc = k
        if v.color == WHITE
            VISIT-BCC(G, v, k)