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.
Graph having 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
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:
| Let disc_time[v] = -1 and explored[v] = false forall v | |
| dfscounter = 0 | |
| DFS(v): | |
| explored[v] = true | |
| disc_time[v] = low[v] = ++dfscounter | |
| foreach edge (v,x): | |
| if !explored[x]: | |
| DFS(x) | |
| low[v] = min(low[v], low[x]) | |
| if low[x] >= disc_time[v]: | |
| print “v is articulation point separating x” | |
| elif x is not v’s parent: | |
| low[v] = min(low[v], disc_time[x]) |
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:
Everything Under The Sun 
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.
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.
Thank you. I read your comment, did a bit of extra reading and got it cleared.
Keep up your good work.
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.
You copied image from here https://courses.cs.washington.edu/courses/cse421/04su/slides/artic.pdf without any reference. You should have given credit where it is due.
It’s already referenced at the end of the post in the references section.
Sir, can u plz suggest some cut vertex detection logic in a dynamic graph, where the neighbours of a node are not static…
What is your use case? After each operation (edge addition, deletion), are you supposed to report the cut vertices? Is this problem part of an ongoing contest?
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.
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.
Why did u use “elif x is not v’s parent:” and not “else:” in line 13??
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.