Strong Bridges and Strong Articulation Points, in depth: the dominator reduction, a verified implementation and a worked example

Why the undirected algorithm does not carry over

The familiar Tarjan low-link algorithm for undirected bridges relies on a fact that fails for directed graphs: in an undirected DFS every non-tree edge goes back to an ancestor, so a subtree is cut off exactly when nothing in it reaches above its root. Directed DFS also produces cross edges and forward edges, and a path out of a subtree and a path back into it are separate requirements. An edge can be essential for reaching a vertex while being irrelevant for leaving it, or the other way round.

That asymmetry suggests the fix. Strong connectivity of a graph G is equivalent to two reachability statements about any chosen root r: every vertex is reachable from r in G, and every vertex reaches r, which is the same as being reachable from r in the reverse graph G^R. Removing an edge or vertex breaks strong connectivity exactly when it breaks one of those two single-source reachability properties. Single-source reachability failures are what dominators describe.

Dominators and flow-graph bridges

Fix a start vertex r of a directed graph in which every vertex is reachable from r; this is called a flow graph G(r). Vertex u dominates v if every path from r to v passes through u. Every vertex dominates itself and r dominates everything. The immediate dominator idom(v) is the closest strict dominator of v, and the idom links form a tree rooted at r, the dominator tree. A vertex is a non-trivial dominator if it dominates some vertex other than itself and is not r; in tree terms, it is an internal vertex other than the root.

The edge analogue is a bridge of the flow graph: an edge (u, v) that every path from r to v must use. Removing it makes v unreachable from r. Two facts connect this to the dominator tree. If (u, v) is such an edge, then u must be idom(v), because every path to v ends in that edge and therefore passes u last. And no other edge into v can offer a detour, so every other predecessor w of v must itself only be reachable through v, meaning v dominates w. Parallel copies of (u, v) are a detour too.

Combining the two reachability conditions gives the theorem the linear-time algorithm rests on. In a strongly connected G with arbitrary root r:

• An edge (u, v) is a strong bridge if and only if it is a bridge of the flow graph G(r) or (v, u) is a bridge of the flow graph G^R(r).
• A vertex v other than r is a strong articulation point if and only if it is a non-trivial dominator in G(r) or in G^R(r).
• The root r itself is a strong articulation point if and only if G minus r is not strongly connected, which one extra linear-time check decides.

A useful corollary bounds the output: each flow graph has at most n - 1 bridges, since each vertex other than r has at most one, so a strongly connected graph has at most 2n - 2 strong bridges no matter how many edges it has.

A complete implementation

Computing dominators is the only non-trivial step. Lengauer-Tarjan runs in O(m α(m, n)) and fully linear algorithms exist, but they are long and easy to get wrong. The iterative algorithm of Cooper, Harvey and Kennedy is twenty lines, is fast on real graphs, and has quadratic worst-case time; use it first and switch only if profiling says so. The implementation below is complete and was checked against the brute-force oracle in the next section on 3,000 random strongly connected graphs.

def dominators(n, edges, r):
    """Cooper-Harvey-Kennedy. Returns idom list with idom[r] == r."""
    succ = [[] for _ in range(n)]; pred = [[] for _ in range(n)]
    for u, v in edges:
        succ[u].append(v); pred[v].append(u)
    order, seen, stack = [], [False] * n, [(r, 0)]
    seen[r] = True
    while stack:                                  # iterative DFS, postorder
        u, i = stack.pop()
        if i < len(succ[u]):
            stack.append((u, i + 1))
            v = succ[u][i]
            if not seen[v]:
                seen[v] = True; stack.append((v, 0))
        else:
            order.append(u)
    rpo = order[::-1]
    num = {u: k for k, u in enumerate(rpo)}
    idom = [None] * n; idom[r] = r

    def intersect(a, b):                          # walk up to common ancestor
        while a != b:
            while num[a] > num[b]: a = idom[a]
            while num[b] > num[a]: b = idom[b]
        return a

    changed = True
    while changed:
        changed = False
        for v in rpo[1:]:
            new = None
            for p in pred[v]:
                if idom[p] is not None:
                    new = p if new is None else intersect(p, new)
            if idom[v] != new:
                idom[v] = new; changed = True
    return idom

def dominates_fn(n, idom, r):
    """O(1) dominance test from pre/post numbers on the dominator tree."""
    kids = [[] for _ in range(n)]
    for v in range(n):
        if v != r: kids[idom[v]].append(v)
    pre, post, t, stack = [0] * n, [0] * n, 0, [(r, False)]
    while stack:
        u, done = stack.pop()
        if done: post[u] = t; t += 1; continue
        pre[u] = t; t += 1
        stack.append((u, True))
        stack.extend((k, False) for k in kids[u])
    return lambda a, b: pre[a] <= pre[b] and post[b] <= post[a]

def flow_bridges(n, edges, r):
    idom = dominators(n, edges, r)
    dom = dominates_fn(n, idom, r)
    mult, preds = {}, [[] for _ in range(n)]
    for u, v in edges:
        mult[(u, v)] = mult.get((u, v), 0) + 1; preds[v].append(u)
    out = set()
    for u, v in edges:
        if v == r or idom[v] != u or mult[(u, v)] > 1:
            continue
        if all(w == u or dom(v, w) for w in preds[v]):
            out.add((u, v))
    return out

def reverse(edges):
    return [(v, u) for u, v in edges]

def strong_bridges(n, edges, r=0):
    back = {(v, u) for u, v in flow_bridges(n, reverse(edges), r)}
    return flow_bridges(n, edges, r) | back

def strong_articulation_points(n, edges, r=0):
    sap = set()
    for g in (edges, reverse(edges)):
        idom = dominators(n, g, r)
        sap |= {idom[v] for v in range(n) if v != r and idom[v] != r}
    rest = [(u, v) for u, v in edges if r not in (u, v)]
    if n > 2 and not strongly_connected(n, rest, skip={r}):
        sap.add(r)
    return sap

The flow_bridges loop looks quadratic but is not: the all(...) test runs only for the single edge per vertex that matches idom[v] == u, so each predecessor list is scanned at most once and the whole function is O(n + m) after dominators. The pre/post interval test answers 'does v dominate w' in constant time. strongly_connected is the two-BFS check shown next.

Testing against a brute-force oracle

Never ship a graph algorithm like this without an oracle. The brute-force version follows the definitions literally and is obviously correct, so randomised agreement between the two is strong evidence the fast version is right.

def reach(n, edges, s, skip=()):
    adj = [[] for _ in range(n)]
    for u, v in edges: adj[u].append(v)
    seen, st = {s}, [s]
    while st:
        u = st.pop()
        for v in adj[u]:
            if v not in seen and v not in skip:
                seen.add(v); st.append(v)
    return seen

def strongly_connected(n, edges, skip=frozenset()):
    alive = [v for v in range(n) if v not in skip]
    if not alive: return True
    need = set(alive)
    return (reach(n, edges, alive[0], skip) >= need and
            reach(n, reverse(edges), alive[0], skip) >= need)

def brute(n, edges):
    sb = {e for i, e in enumerate(edges)
          if not strongly_connected(n, edges[:i] + edges[i + 1:])}
    sap = {v for v in range(n)
           if not strongly_connected(n, [(a, b) for a, b in edges if v not in (a, b)], {v})}
    return sb, sap

Generate random graphs with 2 to 9 vertices, keep the strongly connected ones, and assert that both functions agree. Small graphs are the point: they hit the corner cases such as two-vertex cycles, a root that is itself the articulation point, and edges that are bridges in only one direction. Deduplicate parallel edges in the oracle or count them consistently in both implementations; that one detail is the commonest disagreement.

Worked example by hand

Take root r = 0. In the forward flow graph, the dominator tree has idom(1) = 0, idom(2) = 1, idom(3) = 2, idom(4) = 3 and idom(5) = 3: the only way from 0 into the right part is 0 to 1 to 2 to 3, and vertex 5 can be reached from 3 directly or via 4, so 4 does not dominate it. The non-trivial dominators are 1, 2 and 3. Forward flow bridges are (0,1), (1,2), (2,3) and (3,4). Edge (3,5) is not one: although idom(5) = 3, the other predecessor of 5 is 4, which 5 does not dominate.

In the reverse graph rooted at 0, idom(1) = 0, idom(2) = 0, idom(3) = 4, idom(4) = 2 and idom(5) = 3. Every route back to 0 from the right part goes 3 to 4 to 2 to 0. That adds non-trivial dominators 4, 2 and 3, and reverse bridges which, mapped back to original orientation, are (2,0), (3,4), (4,2) and (5,3).

The union gives seven strong bridges: (0,1), (1,2), (2,0), (2,3), (3,4), (4,2) and (5,3). The three survivors each have a detour: 1 to 0 is redundant because 1 to 2 to 0 exists, and 4 to 5 and 3 to 5 back each other up. Strong articulation points from the two trees are 1, 2, 3 and 4. The root needs the separate check: deleting 0 leaves 1 with no incoming edge, so 0 is one too. Vertex 5 is not, since 0 to 4 stays strongly connected without it. The brute-force oracle agrees on both sets.

Operational guidance

Using the result. In a dependency or network graph, strong bridges are the links to duplicate first and strong articulation points the nodes to make redundant first. Rank them by impact: for each one, the size of the smaller side it cuts off tells you how much of the system loses round-trip reachability. A dominator subtree size, already available from the tree, gives the forward half of that number for free.

Graphs that are not strongly connected. Compute strongly connected components first with Tarjan or Kosaraju, then run the algorithm inside each component. Edges between components are not candidates, because the graph was never strongly connected across them.

Scale. Use the iterative DFS throughout; recursive versions overflow the stack on long chains, which is exactly the shape of graphs with many bridges. For graphs with tens of millions of edges, store adjacency in compressed arrays and run the forward and reverse dominator passes in parallel, since they are independent.

Beyond single failures. The same machinery underlies 2-edge-connected and 2-vertex-connected blocks of directed graphs, studied by Georgiadis, Italiano and co-authors; those answer 'which pairs stay mutually reachable after any single failure', which is what a capacity planner usually wants next.

Failure modes

• Running on a graph that is not strongly connected. Unreachable vertices keep idom as None and the theorem does not apply. Check strong connectivity first and fail loudly.
• Forgetting the root. The dominator theorem says nothing about r; omitting the extra check silently misses it, as vertex 0 in the example shows.
• Ignoring parallel edges. Two copies of (u, v) mean neither is a bridge. Deduplicating the input before analysis gives wrong answers for multigraphs.
• Mapping reverse-graph edges back wrongly. A bridge (v, u) in G^R is the original edge (u, v). Swapping it the wrong way produces edges that are not in the graph at all, so assert membership.
• Using undirected low-link logic. Treating the directed graph as undirected finds bridges of the underlying undirected graph, which is a different and much smaller set.

Trade-offs

What to do next

1. Implement the brute-force oracle first and keep it in your test suite.
2. Add the Cooper-Harvey-Kennedy dominator function and the flow-bridge test, and fuzz-compare on thousands of small random graphs, including multigraphs.
3. Run SCC decomposition before analysis so the input precondition always holds.
4. Rank the strong bridges and articulation points you find by the reachability they cut, and feed the top of that list into your redundancy plan.
5. If profiling shows dominators dominate runtime on large inputs, swap in Lengauer-Tarjan behind the same interface and re-run the oracle tests.

Keep learning: Bridges and articulation points with Tarjan's low-link, Articulation points and the block-cut tree, Tarjan's strongly connected components and Kosaraju's SCC algorithm.