Hopcroft-Tarjan Articulation Points

How articulation-point detection works

An articulation point (cut vertex) is a vertex whose removal increases the number of connected components. In a tree every internal vertex is articulation; in a complete graph none are. Identifying them tells you which network nodes are critical — losing them shatters connectivity.

Hopcroft and Tarjan (1973) showed that a single DFS over the graph suffices. Maintain two values per vertex:

• disc[v] — discovery time when DFS first visits v.
• low[v] — the smallest disc value reachable from v's subtree via tree edges plus at most one back edge.

Two rules detect articulation points:

1. Root rule. The DFS root is articulation iff it has ≥ 2 children in the DFS tree.
2. Non-root rule. A non-root vertex u is articulation iff it has at least one child v in the DFS tree with low[v] ≥ disc[u].

Why the rules work

Non-root case: low[v] ≥ disc[u] means v's subtree cannot reach any vertex discovered earlier than u using a single back edge. So the only way v's subtree connects to the rest of the graph is through u itself. Removing u disconnects v's subtree from everyone else. Conversely, if every child v satisfies low[v] < disc[u], each subtree has an alternative route around u.

Root case: the root is articulation only if there are at least two children — otherwise the rest of the graph hangs off one child and remains connected after the root is removed. With two children, those two subtrees become disconnected from each other.

Worked example — 8-node graph

Consider an 8-node undirected graph forming three "lobes" through a central hub:

  1 — 2        4
  |   |       /
  3 — 4 — 5 — 6
          |
          7 — 8

Run DFS from 1: 1 → 2 → 4 → 3 → (back to 1) → 5 → 6 → 7 → 8 → (back to 7) → (back to 6). Compute disc and low:

Node	disc	low	Parent	DFS children	Articulation?
1	0	0	—	2	No (root, 1 child)
2	1	0	1	4	No (low[4] = 0 < disc[2] = 1)
4	2	0	2	3, 5	Yes (low[5] = 3 ≥ disc[4] = 2)
3	3	0	4	—	No (leaf)
5	4	4	4	6	Yes (low[6] = 5 ≥ disc[5] = 4)
6	5	5	5	7	Yes (low[7] = 6 ≥ disc[6] = 5)
7	6	6	6	8	Yes (low[8] = 7 ≥ disc[7] = 6)
8	7	7	7	—	No (leaf)

Articulation points: {4, 5, 6, 7}. Removing any one of them disconnects the graph. The DFS does 8 vertex visits and ~9 edge checks — O(V + E).

Cost in real terms

On a graph of 1 million vertices and 5 million edges, the articulation-point algorithm finishes in roughly 100 ms in compiled C++ — essentially the cost of one DFS pass. The block-cut tree (collapse biconnected components, keep articulation points) typically has 15–40% as many nodes as the original on real-world social and road networks — a useful sparsified representation.

Hopcroft-Tarjan vs alternatives

	Hopcroft-Tarjan	Naive (remove each vertex)	Block-cut tree (Even-Tarjan)	Random sampling	Link-cut tree (dynamic)
Time	O(V + E)	O(V · (V + E))	O(V + E)	O((V + E) log V)	O(log² V) per update
Finds all articulations	Yes	Yes	Yes (+ blocks)	Probabilistic	Yes (online)
Online (edge additions/removals)	No	No	No	No	Yes
Implementation	One DFS, ~30 LOC	BFS per vertex	One DFS + tree	Karger's contraction	Hard, ~500 LOC
Output	Articulation set	Articulation set	Blocks + cut vertices	Articulation set	Articulation set + dynamic blocks
Use case	Default choice	Pedagogical	Planarity, BCC queries	Approximate, parallel	Network with churn

JavaScript implementation

function findArticulationPoints(graph) {
  const disc = new Map(), low = new Map();
  const parent = new Map();
  const articulations = new Set();
  let timer = 0;

  function dfs(u, isRoot) {
    disc.set(u, timer); low.set(u, timer); timer++;
    let dfsChildren = 0;
    for (const v of graph[u] || []) {
      if (!disc.has(v)) {
        parent.set(v, u);
        dfsChildren++;
        dfs(v, false);
        low.set(u, Math.min(low.get(u), low.get(v)));
        // Non-root articulation rule
        if (!isRoot && low.get(v) >= disc.get(u)) articulations.add(u);
      } else if (v !== parent.get(u)) {
        // back edge
        low.set(u, Math.min(low.get(u), disc.get(v)));
      }
    }
    // Root articulation rule
    if (isRoot && dfsChildren >= 2) articulations.add(u);
  }

  for (const v of Object.keys(graph)) {
    if (!disc.has(v)) dfs(v, true);
  }
  return [...articulations];
}

// Example
const g = {
  1: [2, 3], 2: [1, 4], 3: [1, 4],
  4: [2, 3, 5], 5: [4, 6], 6: [5, 7], 7: [6, 8], 8: [7]
};
console.log(findArticulationPoints(g));  // [4, 5, 6, 7]

Python implementation (iterative)

def find_articulation_points(graph):
    disc, low = {}, {}
    parent, articulations = {}, set()
    timer = 0

    def dfs(start):
        nonlocal timer
        disc[start] = low[start] = timer; timer += 1
        parent[start] = None
        # Iterative DFS to handle deep graphs
        stack = [(start, iter(graph.get(start, ())))]
        children = {start: 0}
        while stack:
            u, it = stack[-1]
            found = False
            for v in it:
                if v not in disc:
                    parent[v] = u
                    disc[v] = low[v] = timer; timer += 1
                    children[v] = 0
                    children[u] = children.get(u, 0) + 1
                    stack.append((v, iter(graph.get(v, ()))))
                    found = True
                    break
                elif v != parent.get(u):
                    low[u] = min(low[u], disc[v])
            if not found:
                stack.pop()
                if stack:
                    parent_u = stack[-1][0]
                    low[parent_u] = min(low[parent_u], low[u])
                    if parent.get(parent_u) is not None and low[u] >= disc[parent_u]:
                        articulations.add(parent_u)
        if children.get(start, 0) >= 2:
            articulations.add(start)

    for v in graph:
        if v not in disc: dfs(v)
    return articulations

Variants and extensions

• Block-cut tree. Contract each biconnected component to a single node and keep articulation points as connector nodes. The result is a tree by construction. Used in planarity testing, in some flow algorithms, and as a sparsified graph for path queries that must avoid certain failures.
• SPQR-tree decomposition. Generalizes the block-cut tree to triconnected components — splits a biconnected graph into series, parallel, and rigid pieces. Used by Hopcroft-Tarjan's linear-time planarity algorithm.
• Online articulation-point maintenance. With link-cut trees and Holm-Lichtenberg-Thorup-style decremental techniques, the articulation set can be maintained under edge additions and deletions in O(log² V) per update.
• k-vertex-connectivity. Articulation points are the 1-cut; finding all minimum vertex cuts (2-cuts, 3-cuts, ...) generalizes via Gabow's ear-decomposition algorithms.
• Simultaneous bridges + articulations. Same DFS pass: bridges from low[v] > disc[u], articulations from low[v] ≥ disc[u] plus the root-children rule. Many production implementations bundle both.

When to use articulation-point detection

• Network resilience. Telecom and ISP planners identify single-points-of-failure nodes; redundancy gets prioritized around articulation points.
• Social-network analysis. Brokers and gatekeepers — nodes that bridge communities — show up as articulation points. The Krackhardt-Stiles betweenness measure correlates strongly with articulation-point status.
• Computer-network routing. Articulation points need backup routes; bridges between routers get duplicated.
• Bioinformatics. In gene regulatory or protein-interaction networks, articulation points often correspond to essential proteins — knocking them out is lethal.
• Planarity testing. Hopcroft-Tarjan's linear-time planarity algorithm uses biconnected-component decomposition as a preprocessing step.

Famous articulation problems

LeetCode 1568 — Min Days to Disconnect Island

Given a grid of land cells (1s) and water cells (0s), return the minimum number of 1s to flip to 0 so the island disconnects (or no longer exists). Answer is at most 2. Step 1: check if it's already disconnected — 0. Step 2: find any articulation cell (treat the grid as a graph); if one exists, the answer is 1. Otherwise 2. Hopcroft-Tarjan gives the articulation test in O(R · C), making the entire solution O(R · C).

Network of schools — Codeforces 911E variant

Given a school computer network, find the smallest set of schools whose loss would split the network. Reduces to: find all articulation points, then identify which subset together form a minimum vertex cut. The 1-cut is exactly the articulation set; 2-cuts require Gabow's 2-vertex-connectivity algorithm.

Common bugs and edge cases

• Forgetting the root rule. The non-root rule low[v] ≥ disc[u] is trivially true for the root's only child (low ≥ 0 = disc[root]), misclassifying any non-leaf root as articulation. The root needs the separate "≥ 2 children" check.
• Updating low through the parent edge. When iterating neighbors of u, skip the immediate parent (the tree edge we just came from). Otherwise low[u] gets pulled down spuriously, missing real articulation points.
• Multi-edges and self-loops. Self-loops contribute nothing; multi-edges to the parent must NOT be treated as back edges (they ARE the parent edge). Track edges by id rather than endpoint to disambiguate.
• Recursion limit. A path graph of 10⁶ nodes blows JavaScript's stack at ~10⁴ frames. Use iterative DFS for production code.
• Confusing articulation points with bridges. Bridges use strict inequality (low[v] > disc[u]); articulations use non-strict (low[v] ≥ disc[u]). A bridge's endpoint is usually but not always an articulation — it depends on degree.
• Disconnected graphs. Run DFS from every unvisited vertex. Each connected component has its own root rule applied.