Bridges (Cut Edges) in Graphs, in depth: chain decomposition, XOR certificates and adding the fewest edges to remove every bridge

One characterisation behind every method

Fix any spanning forest T of the graph, for example a DFS tree. Every edge not in T closes exactly one cycle with the tree path between its endpoints; say that it covers every tree edge on that path. Three statements are then equivalent for an edge e:

1. e is a bridge.
2. e lies on no cycle.
3. e is a tree edge of T and no non-tree edge covers it.

The argument is short. A non-tree edge always lies on its own fundamental cycle, so it is never a bridge. If a tree edge is covered, removing it leaves the covering edge plus the rest of the tree path as a detour, so it is not a bridge. If a tree edge is uncovered, every edge crossing between the two sides of the cut it defines would have to cover it, and there are none, so removing it disconnects them. Every algorithm below is just a fast way to decide which tree edges are covered.

Two inputs break naive code: parallel edges, where two edges join the same pair and neither is a bridge, and self-loops, which cover nothing and are never bridges. Identify edges by index, never by their endpoint pair, and the characterisation handles both. The DFS below is iterative to avoid recursion limits; the technique is explained in iterative DFS.

def dfs_tree(n, edges):
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i)); adj[v].append((u, i))
    depth = [-1] * n; parent = [-1] * n; pedge = [-1] * n; order = []
    for s in range(n):
        if depth[s] != -1:
            continue
        depth[s] = 0; stack = [s]; it = {}; order.append(s)
        while stack:
            u = stack[-1]; k = it.get(u, 0)
            if k < len(adj[u]):
                it[u] = k + 1
                v, eid = adj[u][k]
                if depth[v] == -1:
                    depth[v] = depth[u] + 1; parent[v] = u; pedge[v] = eid
                    order.append(v); stack.append(v)
            else:
                stack.pop()
    return adj, order, parent, pedge, depth

Chain decomposition

Jens Schmidt's 2013 chain decomposition turns the covering idea into a walk. In a DFS tree every non-tree edge is a back edge joining a vertex to one of its ancestors (the reason is covered in DFS tree edge classification). Visit vertices in discovery order. For each back edge leaving an ancestor u towards a descendant v, mark u, take the back edge, then climb tree edges from v upwards until you reach an already-marked vertex. Each such walk is a chain, and every edge it uses is covered. Because the climb stops at the first marked vertex, each edge is walked at most once, so the whole pass is O(V + E).

def bridges_chain(n, edges):
    adj, order, parent, pedge, depth = dfs_tree(n, edges)
    tree = set(e for e in pedge if e != -1)
    visited = [False] * n
    covered = [False] * len(edges)
    for u in order:                      # discovery order
        for v, eid in adj[u]:
            if u == v:
                covered[eid] = True      # a self-loop never disconnects anything
                continue
            if eid in tree or depth[v] <= depth[u]:
                continue                 # handle each back edge once, from its ancestor
            visited[u] = True
            covered[eid] = True
            w = v
            while not visited[w]:        # climb until the chain meets earlier chains
                visited[w] = True
                covered[pedge[w]] = True
                w = parent[w]
    return sorted(i for i in range(len(edges)) if not covered[i])

Why does stopping early never leave a covered edge unmarked? Suppose the climb for back edge (u, v) stops at a vertex w that an earlier chain reached. That earlier chain started at some u' discovered before u, and by induction over earlier chains the tree path from w up to u' is already marked. Both u and u' are ancestors of w, so they lie on one root path, and since u' was discovered first it is the higher of the two. The earlier chain therefore already marked the whole path from w to u. The chains also give more than bridges: a connected graph is 2-edge-connected exactly when the chains cover every edge, and Schmidt shows that in a 2-edge-connected graph the start of every cycle chain after the first is a cut vertex, so one pass yields both kinds of single point of failure.

XOR certificates

The second technique replaces walking with hashing. Give every non-tree edge a random 64-bit label. Label each tree edge with the XOR of the labels of all non-tree edges covering it. That XOR can be computed bottom-up: XOR each non-tree label into both endpoints, and the label of the tree edge above v is the XOR of everything in v's subtree, because a non-tree edge with both ends inside the subtree cancels itself out, and one with exactly one end inside crosses the cut.

import random

def bridges_xor(n, edges, bits=64, rng=random):
    adj, order, parent, pedge, depth = dfs_tree(n, edges)
    tree = set(e for e in pedge if e != -1)
    acc = [0] * n
    for i, (u, v) in enumerate(edges):
        if i not in tree:
            r = rng.getrandbits(bits)
            acc[u] ^= r; acc[v] ^= r      # a self-loop XORs twice and cancels
    label = [0] * len(edges)
    for v in reversed(order):             # children before parents
        if pedge[v] != -1:
            label[pedge[v]] = acc[v]
            acc[parent[v]] ^= acc[v]
    return sorted(e for e in tree if label[e] == 0), label

An uncovered tree edge has label 0 with certainty. A covered one has label 0 only if independent random labels happen to XOR to zero, with probability 2 to the minus 64 per edge. So the method never misses a bridge, and with 64-bit labels its false alarms are negligible. It works with any spanning tree, not just a DFS tree, which is what makes it attractive for parallel and distributed graphs: build a BFS tree or a spanning tree from union-find, then the labels are one subtree-XOR aggregation. A bonus falls out: two edges whose labels are equal and non-zero form a 2-edge cut, because they are covered by exactly the same set of non-tree edges.

Worked example

Take the graph above: triangles {0, 1, 2}, {3, 4, 5} and {6, 7, 8}, joined by e3 = (2, 3) and e7 = (4, 6), plus a self-loop e11 on vertex 1. DFS from 0 builds tree edges e0, e1, e3, e4, e5, e7, e8 and e9; the back edges are e2, e6, e10 and the self-loop. Chain decomposition starts at vertex 0 with back edge e2, climbs from 2 through e1 and e0 back to 0, and covers the first triangle. Vertex 3 starts a chain with e6 covering e5 and e4, and vertex 6 starts one with e10 covering e9 and e8. Edges e3 and e7 are never walked, so they are the bridges.

Running the XOR version with deliberately tiny 8-bit labels makes the arithmetic visible. The tree-edge labels came out as e0 = 82, e1 = 82, e3 = 0, e4 = 242, e5 = 242, e7 = 0, e8 = 38 and e9 = 38. The zeros are the bridges. The equal pairs are the 2-edge cuts inside each triangle: removing e0 and e1 isolates vertex 1. The self-loop's label XORed into vertex 1 twice and vanished, as it should.

From bridges to a bridgeless network

Finding bridges is usually the first step; removing them is the goal. Contract each 2-edge-connected component to a node, and the bridges form a tree, the bridge tree. Every bridge-tree leaf needs at least one new edge leaving it, and one edge serves at most two leaves, so a connected graph whose bridge tree has L leaves needs at least ceil(L/2) new edges. Eswaran and Tarjan proved in 1976 that ceil(L/2) always suffices. A construction: list the leaves in DFS order of the bridge tree, then join leaf i to leaf i + ceil(L/2). Pairing leaves that are far apart in DFS order makes every bridge's tree path lie under at least one new edge.

def augment(n, edges):
    br = bridges_chain(n, edges)
    cid, k, tedges = bridge_tree(n, edges, br)   # union-find over non-bridges
    if k == 1:
        return []
    deg = [0] * k; tadj = [[] for _ in range(k)]
    for a, b in tedges:
        deg[a] += 1; deg[b] += 1; tadj[a].append(b); tadj[b].append(a)
    root = next((x for x in range(k) if deg[x] > 1), 0)
    leaves, seen, st = [], {root}, [root]
    while st:                                    # leaves in DFS order
        x = st.pop()
        if deg[x] == 1:
            leaves.append(x)
        for y in reversed(tadj[x]):
            if y not in seen:
                seen.add(y); st.append(y)
    rep = {}
    for v in range(n):
        rep.setdefault(cid[v], v)                # any vertex inside each component
    L = len(leaves); h = (L + 1) // 2
    return [(rep[leaves[i]], rep[leaves[(i + h) % L]]) for i in range(h)]

On the worked example the bridge tree is a path A to B to C with two leaves, so one edge suffices, and the code returns (0, 6). Adding it puts both bridges on a cycle, and a re-run finds no bridges. In practice the endpoints matter: a cable between two buildings costs more than one inside a room, so treat the pairing as a lower bound and a starting plan, and weight the choice of representative vertices by cost.

Testing against an oracle

A bridge finder is easy to test because the definition is executable: delete each edge in turn and count components. That is O(E(V + E)), far too slow for production and perfect as an oracle. Generate small random multigraphs that include self-loops, parallel edges and isolated vertices, and require all implementations to agree:

R = random.Random(1)
for t in range(3000):
    n = R.randint(1, 9); m = R.randint(0, 14)
    E = [(R.randrange(n), R.randrange(n)) for _ in range(m)]
    expected = bridges_brute(n, E)
    assert bridges_chain(n, E) == expected
    assert bridges_xor(n, E, rng=R)[0] == expected
    if components(n, E) == 1 and n > 1:
        assert bridges_brute(n, E + augment(n, E)) == []

All three functions above pass 3,000 such graphs. The first draft of the chain version did not: it reported self-loops as bridges, because a self-loop is neither a tree edge nor a back edge to a descendant and was never marked covered. The oracle found it on the first run, which is the argument for writing one. To see the XOR method's probabilistic nature, shrink the labels to 8 bits: across 2,000 random 30-vertex graphs it reported a covered edge as a bridge on 154 of them. At 64 bits the same experiment has no realistic chance of an error.

Failure modes

• Edges keyed by endpoints. A set of (u, v) pairs merges parallel edges and turns two redundant links into one false bridge.
• Skipping the parent vertex instead of the parent edge. The same parallel-edge bug, in low-link code; skip the edge id you arrived by.
• Recursion depth. A path-like graph of a million vertices overflows a recursive DFS; use the iterative form.
• Disconnected input. Start a DFS from every unvisited vertex, and run augmentation per component after connecting them.
• Short random labels. 32-bit labels on a billion-edge graph give real collisions; use 64 bits or two independent labels.
• Directed graphs. None of this applies to reachability in directed graphs; that problem needs dominators, as in strong bridges.

Trade-offs

For a single machine and a static graph, either linear DFS method is fine; choose the one your team can verify. For a graph partitioned across workers, or when you also want 2-edge cuts, XOR labels win. For cut vertices as well as cut edges, see articulation points.

What to do next

1. Implement the brute-force oracle first, including self-loops and parallel edges in the generator.
2. Implement one linear-time method keyed by edge index, and stress-test it against the oracle.
3. If the graph is distributed or you need 2-edge cuts, add 64-bit XOR labels over any spanning tree.
4. Build the bridge tree with union-find over non-bridge edges and count its leaves L.
5. Plan ceil(L/2) new links by pairing leaves in DFS order, then adjust endpoints for cost and re-run the check.
6. Re-run bridge detection whenever topology changes, and alert when a new bridge appears.