9.16 Articulation Points
You need to find vertices whose removal disconnects an undirected graph.
9.16 Articulation Points
Problem
You need to find vertices whose removal disconnects an undirected graph.
In many networks, some vertices are structurally more important than others. A router may connect two regions of a network. A bridge station may connect two subway lines. A person may connect two otherwise separate social groups. A package may sit between independent parts of a dependency graph.
You need to identify vertices that act as single points of failure.
Solution
Use DFS with discovery times and low-link values.
An articulation point, also called a cut vertex, is a vertex whose removal increases the number of connected components.
Consider:
A -- B -- C
|
D
Removing B separates the graph into:
A
C
D
So B is an articulation point.
Removing A, C, or D does not disconnect the remaining graph.
Discussion
Articulation points measure fragility.
They answer the question:
Which vertices hold the graph together?
This is useful in:
| Domain | Articulation point meaning |
|---|---|
| Networks | Critical router or switch |
| Transportation | Critical station or junction |
| Social graphs | Broker between communities |
| Infrastructure | Single point of failure |
| Program graphs | Critical control-flow node |
The naïve approach is simple: remove each vertex, run connectivity analysis, and check whether the component count increases. That works, but it is expensive.
For each vertex, a full DFS costs O(V + E). Repeating that for all vertices gives:
O(V(V + E))
A better algorithm finds all articulation points in one DFS.
DFS Tree View
Run DFS on an undirected graph.
DFS creates a tree of discovery edges.
Example graph:
A -- B -- C
|
D
A DFS from A might produce:
A
|
B
|\\nC D
The question becomes:
Can a child subtree reach an ancestor without going through its parent?
If not, the parent is an articulation point.
For example, if the subtree rooted at C cannot reach A without going through B, then removing B separates C.
Discovery Time and Low-Link
Each vertex receives a discovery time.
disc[v] = time when v is first visited
Each vertex also receives a low-link value.
low[v] = earliest discovery time reachable from v or its descendants
using zero or more tree edges followed by at most one back edge.
This compact value captures whether a subtree can reach an ancestor.
If a child to of vertex v has:
low[to] >= disc[v]
then the subtree rooted at to cannot reach an ancestor of v.
Therefore, v is an articulation point, except for the special root case.
Root Case
The DFS root has no parent.
For the root, the rule is different.
A DFS root is an articulation point if it has more than one DFS child.
Example:
A
/ \\n B C
If DFS starts at A and discovers both B and C as separate children, then removing A separates the graph.
If the root has only one DFS child, removing it does not split the discovered component.
Recipe: Find Articulation Points
def articulation_points(graph):
time = 0
disc = {}
low = {}
parent = {}
result = set()
def dfs(vertex):
nonlocal time
disc[vertex] = time
low[vertex] = time
time += 1
child_count = 0
for neighbor in graph[vertex]:
if neighbor not in disc:
parent[neighbor] = vertex
child_count += 1
dfs(neighbor)
low[vertex] = min(
low[vertex],
low[neighbor]
)
if vertex not in parent:
if child_count > 1:
result.add(vertex)
else:
if low[neighbor] >= disc[vertex]:
result.add(vertex)
elif parent.get(vertex) != neighbor:
low[vertex] = min(
low[vertex],
disc[neighbor]
)
for vertex in graph:
if vertex not in disc:
dfs(vertex)
return result
Example:
graph = {
"A": ["B"],
"B": ["A", "C", "D"],
"C": ["B"],
"D": ["B"],
}
print(articulation_points(graph))
Output:
{'B'}
Why the Test Works
Consider an edge in the DFS tree:
v
|
to
If:
low[to] < disc[v]
then the subtree rooted at to can reach an ancestor of v.
Removing v does not necessarily isolate that subtree.
But if:
low[to] >= disc[v]
then the subtree cannot climb above v.
Every path from that subtree to earlier vertices passes through v.
Removing v disconnects it.
That is exactly the articulation-point condition.
Recipe: Naïve Checker for Tests
The efficient algorithm is subtle. It is useful to have a slow implementation for testing.
def count_components_without(graph, removed):
visited = set()
def dfs(vertex):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor == removed:
continue
if neighbor not in visited:
dfs(neighbor)
count = 0
for vertex in graph:
if vertex == removed:
continue
if vertex not in visited:
dfs(vertex)
count += 1
return count
Then:
def articulation_points_slow(graph):
original = count_components_without(
graph,
removed=None
)
result = set()
for vertex in graph:
after = count_components_without(
graph,
removed=vertex
)
if after > original:
result.add(vertex)
return result
Use this version to validate the optimized implementation on small random graphs.
Disconnected Graphs
Articulation points are defined component by component.
A graph may already be disconnected:
A -- B -- C
D -- E
The DFS must launch from every unvisited vertex.
The implementation above handles this with:
for vertex in graph:
if vertex not in disc:
dfs(vertex)
Without this loop, articulation points in later components would be missed.
Common Example
Consider:
A -- B -- C
|
D -- E
Articulation points:
B
D
Removing B separates A from the C-D-E region.
Removing D separates E.
Removing C does not disconnect the remaining graph.
Removing A does not disconnect the remaining graph.
Complexity Analysis
Let:
V= number of verticesE= number of edges
The DFS processes each vertex once and each undirected edge twice.
| Operation | Complexity |
|---|---|
| Compute discovery times | O(V + E) |
| Compute low-link values | O(V + E) |
| Find articulation points | O(V + E) |
| Memory usage | O(V) |
The algorithm is linear in graph size.
This makes it suitable for large sparse networks.
Common Pitfalls
Do not use the directed-graph SCC algorithm here. Articulation points are usually defined for undirected graphs.
Do not forget the special root rule.
Do not treat the parent edge as a back edge.
Do not stop after one DFS if the graph is disconnected.
Do not use low[neighbor] > disc[vertex] for articulation points. The correct non-root condition is:
low[neighbor] >= disc[vertex]
The strict version belongs to bridge detection, covered next.
Do not ignore isolated vertices. They are not articulation points because removing them does not increase the number of connected components among the remaining vertices.
Takeaway
Articulation points identify vertices whose removal disconnects an undirected graph. They expose single points of failure in networks, transportation systems, infrastructure graphs, and communication structures. The efficient algorithm uses one DFS, discovery times, and low-link values to determine whether child subtrees can reach ancestors without passing through their parent. This low-link pattern is a recurring tool in advanced graph algorithms.