Articulation Points or Cut Vertices in a Graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. It can be thought of as a single point of failure. Any graph that contains an articulation point is inherently fragile because deleting that single vertex causes a loss of connectivity between other nodes. If a graph does not have an articulation point, then it is said to be biconnected.

Articulation points

Graph having articulation points

A triangle has no articulation points

Graph having no articulation points

Testing for articulation points by brute force is easy. Temporarily delete each vertex u, and then do a BFS or DFS traversal of the remaining graph to establish whether it is still connected. The time complexity of this method is O(V(E + V)). There is a clever linear-time algorithm, however, that tests all the vertices of a connected graph using a single depth-first search.

The algorithm utilizes the properties of the DFS tree. In a DFS tree, a vertex u is parent of another vertex v if v is discovered by u. A vertex u is articulation point iff one of the following two conditions is true:

  • u is the root of the DFS tree and has at least two children
  • u is not the root and no vertex in the subtree rooted at one of the children of u has a back edge to an ancestor of u
Conditions for a vertex to be an articulation point

Conditions for a vertex to be an articulation point

Let disc_time[u] be the time at which a vertex u was discovered/explored during the dfs traversal. Let low[u] be the earliest discovery time of any vertex in the subtree rooted at u or connected to a vertex in that subtree by a back edge. Then

  • If some child x of u has low[x] ≥ disc_time[u], then u is an articulation point.
  • low[u] = min( {low[v] | v is a child of u} ∪ {disc_time[x] | (u, x) is a back edge from u} )

This gives rise to the following algorithm for finding all articulation points:

The time and space complexity of the algorithm is same as than of DFS i.e., O(V + E).

Take a look at C++ implementation.

Try your hand at problem KINGCON which uses this idea.

References:

17 thoughts on “Articulation Points or Cut Vertices in a Graph

  1. Your code is overall very good, but I found a bug:

    You memoize getArticulationPoints() using the variable `done’, which is smart, but you need to add the line `done = false;’ to addEdge(). Otherwise, someone could call getArticulationPoints() and then add an edge to the graph that makes it have more or fewer articulation points, and getArticulationPoints() won’t register the change.

    • I wrote this code for explaining the algorithm described in the post and did not anticipate all the ways a client could break it. Just adding ‘done = false;’ to addEdge() won’t work because the function dfs() has other dependencies: explored, articulation_point and parent. These will have to be reinitialized too.

      I had thought that the only use-case scenario for this code was to call getArticulationPoints() only after all the edges in the graph had been added.

  2. can you plz exaplin why can’t we write
    low[v] = min(low[v], low[x])
    insteat of
    low[v] = min(low[v], disc_time[x])
    in line no 14.

    • Because that is not the definition of low[]. low[u] is the earliest discovery time of any vertex in the subtree rooted at u or connected to a vertex in that subtree by a back edge.

      In any case, we’ve already set low[v] to minimum of low[v] and low[x] at line 10. If we change line 14, it won’t just be wrong but also won’t do anything.

  3. Hi Kartik! Can you please explain why are you taking disc_time instead of low time in else if condition.
    ie: low[v] = min(low[v], disc_time[x]) ==> low[v] = min(low[v], low[x]) as we can reach to more lower number of vertex from v.

    • It won’t make any difference. If you find an edge to an explored node, that node is already on the path from the root (i.e., you actually reached the current node from the explored node).

      That also means that low[] value for that explored node hasn’t been calculated completely yet, not that it would’ve made any difference any way.

  4. Why is root having > 1 child articulate point?
    Say it has 2 children and say there is a backedge from subtree rooted at child1 to subtree rooted at child , then removing root wont make the graph disconnected…

    • We are talking about root of a DFS-traversal tree of a graph. Suppose the root has 2 children and there is an edge from the subtree rooted at child1 to a node x in the subtree rooted at child2, then while doing the DFS traversal from child1, we would have discovered the node x. The only way for child2 to be at depth 1 from the root would be if there is no node in the subtree rooted at child1 that can reach child2, which makes the root an articulation point.

  5. Can u please explain, why we’re using
    “else if (*v != parent[u])
    low[u] = min(low[u], disc_time[*v]);”
    and not “else” only???

    • It’s an undirected graph. If we don’t have this condition, then the whole graph will have the same value for low[], which is 1 because each child node is connected to its parent.

      What we are trying to do with comparison between low[x] and disc_time[v] is determine whether any node in the subtree of a newly discovered vertex x is connected to some vertex above its parent v. If not, then v must be a cut vertex.

      I guess you must have been thrown off by the definition of low[]. A back edge is an edge that goes above a node’s parent in the DFS tree.

    • It’s an undirected graph. If we don’t have this condition, then the whole graph will have the same value for low[], which is 1 because each child node is connected to its parent.

      What we are trying to do with comparison between low[x] and disc_time[v] is determine whether any node in the subtree of a newly discovered vertex x is connected to some vertex above its parent v. If not, then v must be a cut vertex.

      I guess you must have been thrown off by the definition of low[]. A back edge is an edge that goes above a node’s parent in the DFS tree.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s