Articulation Points (Cut Vertices), in depth: an iterative DFS that ranks single points of failure, and the block-cut tree

What a cut vertex is, and how it differs from a bridge

Take an undirected graph G. Vertex v is an articulation point if G minus v (the vertex and all its edges) has more connected components than G. A graph with no articulation points and at least three vertices is biconnected: between any two vertices there are two paths sharing no vertex except their ends. Menger's theorem says the two definitions agree.

Cut vertices and bridges are related but not the same. A bridge is an edge whose removal disconnects the graph. Each endpoint of a bridge is a cut vertex unless it has degree one. A cut vertex need not touch any bridge, though. Two triangles that share one vertex have no bridges, yet the shared vertex is a cut vertex. So a bridge finder cannot stand in for this algorithm.

Brute force removes each vertex and reruns BFS, at O(V(V + E)) total. That is hopeless at scale, but keep it as a test oracle. The DFS method below is O(V + E).

The DFS insight: discovery time, low value and two rules

Run DFS and record disc(v), the time v was first visited. In an undirected graph every non-tree edge joins a vertex to one of its ancestors or descendants. There are no cross edges, which is why the method works (see DFS edge classification). Define low(v) as the smallest discovery time reachable from v by going down tree edges any number of times and then taking at most one back edge.

Now the two rules. Non-root v is a cut vertex if it has a DFS child c with low(c) >= disc(v). Nothing in c's subtree has a back edge to a proper ancestor of v, so every path from that subtree to the rest of the graph goes through v. The root is a cut vertex if it has two or more DFS children. Its children's subtrees cannot be joined by any edge, because that edge would be a cross edge, and DFS would have entered the second subtree from the first.

Both rules count the same thing. Call child c of v separated if low(c) >= disc(v). For the root every child is separated, since nothing has a smaller disc. Removing v leaves one piece per separated child, plus one more for the part above v if v is not the root. If you also track subtree sizes during the DFS, you get the size of each piece for free.

An iterative implementation that measures the damage

The recursive version is ten lines long, but CPython's default recursion limit is 1,000. A path of 5,000 microservices, or any long chain in a road graph, raises RecursionError. Raising the limit just moves the crash into a C-stack overflow. The version below keeps an explicit stack of (vertex, parent edge, next neighbour index) frames, the same pattern as iterative DFS with an explicit stack. The post-order step runs when a frame has no neighbours left, and that is where the child reports to its parent.

def articulation_points(n, edges):
    """Return {v: [sizes of the pieces cut off from v's component when v is removed]}."""
    adj = [[] for _ in range(n)]
    for eid, (u, v) in enumerate(edges):
        adj[u].append((v, eid))
        adj[v].append((u, eid))
    disc = [-1] * n            # discovery time, -1 = unvisited
    low = [0] * n              # lowest disc reachable via subtree + one back edge
    size = [1] * n             # DFS-subtree size
    cut_off = [[] for _ in range(n)]   # sizes of child subtrees v separates
    comp = [0] * n             # size of v's connected component
    timer = 0
    for root in range(n):
        if disc[root] != -1:
            continue
        disc[root] = low[root] = timer
        timer += 1
        members = [root]
        stack = [(root, -1, 0)]          # (vertex, parent edge id, next adj index)
        while stack:
            v, pe, i = stack[-1]
            if i < len(adj[v]):
                stack[-1] = (v, pe, i + 1)
                w, eid = adj[v][i]
                if eid == pe:            # skip only the edge we arrived by
                    continue
                if disc[w] == -1:        # tree edge: descend
                    disc[w] = low[w] = timer
                    timer += 1
                    members.append(w)
                    stack.append((w, eid, 0))
                else:                    # back edge (or the far end of one)
                    low[v] = min(low[v], disc[w])
            else:                        # v finished: report to its parent
                stack.pop()
                if stack:
                    u = stack[-1][0]
                    low[u] = min(low[u], low[v])
                    size[u] += size[v]
                    if low[v] >= disc[u]:
                        cut_off[u].append(size[v])
        for v in members:
            comp[v] = len(members)
    result = {}
    for v in range(n):
        pieces = list(cut_off[v])
        rest = comp[v] - 1 - sum(pieces)  # the part still attached above v
        if rest > 0:
            pieces.append(rest)
        if len(pieces) >= 2:
            result[v] = sorted(pieces, reverse=True)
    return result

Three details matter. First, the parent is skipped by edge id, not by vertex. For cut vertices this makes no difference: a second parallel edge from c to v only offers disc(v), which cannot change the low(c) >= disc(v) test. It matters the moment you reuse this DFS for bridges, where a doubled edge is not a bridge. Second, self-loops are harmless: the loop shows up as a back edge to v itself and cannot lower low(v). Third, the piece above v is computed by subtraction from the component size, so the result covers disconnected inputs too. Removing v only splits v's own component.

Worked example: ranking failures in a service graph

Here is a small service graph: a load balancer lb in front of api; api calls auth (which reads db, and api reads db directly too), cache, queue and search; queue feeds worker; worker and queue both talk to mail; search reads index. Number the vertices lb=0 through index=9 and run the function on the eleven edges:

names = ["lb", "api", "auth", "db", "cache", "queue", "worker", "mail", "search", "index"]
E = [(0,1), (1,2), (2,3), (1,3), (1,4), (1,5), (5,6), (6,7), (5,7), (1,8), (8,9)]
articulation_points(10, E)
# -> {1: [3, 2, 2, 1, 1], 5: [7, 2], 8: [8, 1]}     i.e. api, queue, search

Read the result as an outage report. Losing api leaves five pieces: queue-worker-mail (3), auth-db (2), search-index (2), cache (1) and lb (1). Nothing survives together that is bigger than three vertices. Losing queue cuts off worker and mail (2) from the other seven. Losing search strands only index. auth is not a cut vertex, because db has a second edge to api. That back edge gives low(db) = 1, which is less than disc(auth) = 2, so db's subtree can climb past auth.

Now add a second api replica, api2, connected to lb, auth, cache, queue and search, and run the function again. The result is queue: [8, 2] and search: [9, 1]. api has dropped out. The redundancy removed the worst failure. A useful single severity score is the number of vertices left outside the largest surviving piece: component size - 1 - max(pieces). Before the fix api scores 6, queue 2 and search 1. After it the worst is queue at 2. Sort by this score and fix the top of the list first.

lb is never reported, because nothing hangs off it in this model. Add a users vertex attached to lb and lb becomes a cut vertex at once. The algorithm finds only the single points of failure that you put into the graph.

Beyond a list: biconnected components and the block-cut tree

A cut-vertex list answers whether one vertex can split the graph. The follow-up questions are about paths. Does every route from client X to database Y pass through gateway Z? Which groups of services stay mutually reachable if any single node dies? The block-cut tree answers both.

Split the edges into biconnected components (blocks): maximal sets of edges where any two edges lie on a common simple cycle, or a lone bridge edge. Add a tree node per block and one per cut vertex, and join each cut vertex to every block that contains it. The result is a tree, or a forest for a disconnected graph. Every path from a to b in G passes through cut vertex z exactly when z lies on the tree path between the blocks of a and b. With LCA preprocessing, each such query takes O(1) or O(log V).

To build the blocks, extend the same DFS with a stack of edges. Push each tree edge and each back edge to an ancestor as you traverse it. When a child c of v is separated (low(c) >= disc(v)), pop edges up to and including (v, c). Those edges form one block. The change to the code above is about ten lines and the cost stays O(V + E).

Testing against a brute-force oracle, and at scale

Graph code fails in subtle ways, so test it the boring way. The oracle deletes each vertex, runs BFS, and lists the component sizes inside v's original component. Then compare whole dictionaries, piece sizes included, not just the set of cut vertices. The code above was checked that way on 3,000 random graphs with 1 to 12 vertices and up to 20 random edges. Those graphs included self-loops, parallel edges, isolated vertices and disconnected inputs, and every dictionary matched.

Then test scale. A path of one million vertices is the worst case for recursion. On it the function returns 999,998 cut vertices, every vertex except the two ends, in a few seconds of CPython on a laptop. For graphs with tens of millions of edges, put the adjacency in CSR arrays (an offsets array plus a neighbour array) instead of lists of tuples. Memory, not time, is the first limit you will hit.

Operational guidance and trade-offs

Model before you compute. Decide whether vertices are hosts, services, availability zones or teams. A cut vertex in a host graph can disappear in the zone graph, and the reverse also happens. Include the clients and the external dependencies (DNS, identity provider, payment API), or their single points of failure will be invisible.

Direction matters. All of the above is for undirected reachability. Service calls are directed, and the right questions there are different. Which vertices lie on every path from an entry point? That is the dominator tree. Which vertices break strong connectivity? Those are strong articulation points. Both have linear-time algorithms of their own. Making directed edges undirected and running this code gives a useful first approximation, but it misses asymmetric failures.

One failure versus two. Biconnected means that no single vertex failure disconnects the graph. Surviving any k-1 failures is k-vertex-connectivity, which you test with max-flow on a split-vertex graph (Menger's theorem again; see max-flow min-cut). That costs much more than O(V + E), so run it on the reduced block-cut tree or on the critical subgraph only.

Changing graphs. One run costs O(V + E), so recomputing on every deploy is usually cheaper than a dynamic structure. Diff against the previous output and alert when a new cut vertex appears or a piece grows.

Failure modes

• Using low(c) > disc(v) instead of >=. That is the bridge condition. Mixing the two up silently drops cut vertices whose child can climb exactly back to v.
• Applying the non-root rule to the root. The root always passes the >= test, so it gets reported even with a single child. The piece-count formulation handles this automatically.
• Starting DFS once. On a disconnected graph only the first component is analysed. Loop over all unvisited roots.
• Treating the list as the answer. A cut vertex that cuts off one test box and one that splits the fleet in half look the same in a list. Rank them by vertices stranded outside the largest piece.

What to do next

1. Type in the function and run it against the brute-force oracle on a few thousand random graphs, with self-loops and parallel edges, before you trust it.
2. Export your own service or network topology as an edge list and include the clients and external dependencies. Rank cut vertices by how many vertices each would strand outside the largest surviving piece.
3. Add the edge stack and build the block-cut tree. Then answer one real question with it: "does every path from the checkout service to the database pass through X?"
4. Rerun the analysis in CI on every topology change and fail the build when a new cut vertex appears in the critical subgraph.
5. For directed call graphs, compute dominators from each entry point and compare them with the undirected result.
6. Keep learning: bridges and articulation points with Tarjan's low-link, iterative DFS, DFS edge classification, max-flow min-cut and BFS and DFS fundamentals.