Articulation Points

An articulation point (or cut vertex) is a vertex whose removal disconnects the graph or increases its number of connected components. Finding articulation points identifies single points of failure in a network.

How it works

Tarjan's DFS-based method visits every vertex once, tracking each vertex's discovery time and low-link value, the earliest discovered vertex reachable from its subtree via back edges. A non-root vertex v is an articulation point when some child subtree cannot reach above v, that is low[child] >= disc[v]. The DFS root is an articulation point when it has two or more DFS children. The whole analysis runs in O(V + E).

Applications

Articulation points expose critical routers in communication networks, key intersections in road systems, vulnerable servers in distributed infrastructure, and influential brokers in social networks. Reliability engineering uses them to prioritize redundancy. They also appear in harder interview rounds together with bridges.