Proofs: Online bridge finding

Online bridge finding keeps the 2-edge-connected components and the bridge forest full

This proof shows: correctness.

Let $G$ be the current multigraph. An edge is a bridge if it lies on no cycle, which is the same as: removing it increases the number of connected components. Two vertices are 2-edge-connected if they are equal or joined by two edge-disjoint paths; this is an equivalence relation, and its classes are the 2-edge-connected components. The edges between different classes are exactly the bridges, and contracting each class gives a forest $F(G)$, the bridge forest, whose edges are the bridges [standard facts; see the page on two-edge-connected components].

Invariant (B). (1) The sets of $E$ are the 2-edge-connected components of $G$. (2) The representatives with their pointers $E.\mathrm{find}(\mathrm{par}(a))$ form a rooted forest isomorphic to $F(G)$. (3) The sets of $C$ are the connected components of $G$, each with its number of vertices, and every vertex of a tree of the forest finds the same $C$-root. (4) The counter equals the number of bridges of $G$.

At the start $G$ has no edges, every vertex is its own component and its own tree, and there are no bridges, so (B) holds. Assume (B) before ADD-EDGE$(u, v)$, and let $G' = G + \{u, v\}$, $a = E.\mathrm{find}(u)$, $b = E.\mathrm{find}(v)$.

Case 1: $a = b$ (line L1). Then $u$ and $v$ are 2-edge-connected in $G$. Adding an edge between them creates no new connection between classes and adds no cycle through a bridge: a cycle in $G'$ through a bridge $e$ of $G$ would use the new edge, and replacing the new edge by a path inside the class of $u$ that avoids $e$ (the class has no bridges inside it, and $e$ is not inside it) gives a closed walk in $G$ through $e$ once, so a cycle through $e$ in $G$, a contradiction. So the classes and the bridges are unchanged, and nothing changes.

Case 2: $a \ne b$ and different connected components (lines L3 to L5). The new edge joins two components of $G$, so it lies on no cycle of $G'$: a cycle through it would need another path between the two components. So it is a bridge of $G'$. Every old bridge stays a bridge, because a cycle of $G'$ that uses an old edge cannot use the new bridge, so it would be a cycle of $G$. Every class is unchanged, because the new edge adds no edge-disjoint pair of paths between any two vertices. So $F(G')$ is $F(G)$ plus the edge between the classes $a$ and $b$, and the counter is right after line L3. REROOT$(a)$ (line L9) reverses the pointers on the path from $a$ to the root of its tree: this is the same tree rooted at $a$, so (B2) still holds with $a$ as the root. Setting $\mathrm{par}(a) \leftarrow b$ hangs that tree below $b$, which adds exactly the new bridge to the forest. The union in $C$ merges the two connected components and adds their sizes. In the implementation, REROOT also points the $C$-entries of the path and the old $C$-root at $a$, so all vertices of the rerooted tree reach the root $a$, and then $a$ points to $b$; this keeps (B3).

Case 3: $a \ne b$ in the same connected component (line L6). Then $a$ and $b$ are in one tree $T$ of the forest by (B2) and (B3). Let $P$ be the path $a = x_0, x_1, \ldots, x_k = b$ in $T$, through the lowest common ancestor $l$, and let $e_1, \ldots, e_k$ be its bridges.

Line L7 finds $l$. The climbs visit the ancestors of $a$ and of $b$ in order of distance. A component is marked twice only if it is an ancestor of both, and the first common ancestor reached by either climb is $l$: a climb reaches $l$ before any higher common ancestor, and when one climb reaches a component already marked by the other, that component is a common ancestor; the first such is the lowest one on the climbing side, which is $l$, since every proper ancestor of $l$ is above $l$ on both sides.

The new classes. Each bridge $e_i$ lies on a cycle of $G'$: take the new edge, then a path in $G$ from $v$ to $u$ that crosses the classes of $P$ in order and uses each $e_i$ once (it exists because each class is connected). So no $e_i$ is a bridge of $G'$, and the classes $x_0, \ldots, x_k$ become one 2-edge-connected class of $G'$: any two of their vertices are joined by two edge-disjoint paths, around the new cycle and inside the classes. Every other bridge $f$ of $G$ is not on $P$, so it still separates $T$ into two parts, one of which contains all of $P$; any cycle of $G'$ through $f$ would use the new edge, whose ends are both in the other part, so it would cross $f$ twice, which a cycle cannot. So $f$ stays a bridge, and the other classes do not change.

Line L8 unions exactly the classes $x_i \ne l$ on $P$ into the class of $l$ and decreases the counter once per class merged, that is, $k$ times, once per bridge $e_i$. So (B1) and (B4) hold. In $F(G')$, the merged class is adjacent to the parent of $l$ and to the children of the classes of $P$ that are not on $P$. The merged representative takes the parent of $l$, and the children of the other classes of $P$ still point to vertices of those classes, which now find the merged representative. So (B2) holds. The connected components do not change, and the $C$-pointers still lead to the same root, so (B3) holds.

Queries. By (B1), two vertices are 2-edge-connected if and only if $E.\mathrm{find}$ gives the same representative, and an inserted edge is a bridge if and only if its ends are in different classes. By (B3) and (B4), the connectivity queries and the bridge count are right. $\blacksquare$