Articulation Point: A different approach

This blog post takes a different approach to calculating articulation points in a graph.

Note : This blog post is heavily derived from one of the blog post from the codeforces website. I have basically explained the author’s approach and how it is different from the other approaches that is taken for calculating the articulation points and bridges.

So, what is an articulation point?

An articulation point is a point in a graph, which when removed from the graph results in disjoint graph components. A practical example of articulation points would be critical points in a network graph, whose removal might create a whole system shutdown.

This blog post takes a different approach while calculating articulation points in a graph. I have tried to explain the calculation of the articulation point in a graph using the author’s approach.

The DFS Tree

Those who have not heard about the DFS tree here is a short explanation about it. While I haven’t found an intuitive explanation of why the classical algorithms work for finding the articulation points, here I present you with an intuitive approach for calculating them.

DFS Tree is a tree of vertex traversal formed when we perform a depth-first search in a graph. Let’s say, we have a graph —

Animation of formation of DFS Tree. Taken from here

And we perform the depth-first search on it, we get the following tree. Note that the bold line refers to the path traversed by the dfs, and the light lines refer to the other paths that connect the vertices(later we will know that these are back-edges).

So our DFS tree looks like —

Now by looking at the DFS Tree, we can say that there are few light lines that are present. We can define them as a back-edge between a parent vertex p and child vertex u. If we get a path from p->u other than the edge pu, then we have a back edge.

I have drawn out the DFS Tree in a whiteboard to demonstrate the key facts in it —

Concentrate on the left part!

We have broken down our traversal of the graph into a dfs tree, and in the dfs tree, we have the set of a vertex in a certain level of dfs. You can see the vertex 3and 9in level 2.

Now there are certain facts that we can observe before we move on to the articulation point.

• We can easily find the back-edge in a graph through the light edges in a dfs tree.
• The DFS tree simplifies the connection of a given vertex. Once we draw out a dfs tree, we can get a concise view without distorting the connection between the vertex. It is a simplified view of connections in a graph.

With these two facts, we can code up our implementation for calculating the articulation point. We can use the fact that counting the number of light edges in the graph(in the dfs tree) and return the no. of back edges in a graph. The problem is reduced into an intuitive one.

Note : The example graph out here, contains no bridges and articulation points. So don’t get surprised if you get zero bridges!

Calculating Articulation Points and Bridges

Calculating the number of bridges

As the dfs tree makes finding the articulation points and bridges quite intuitive, we now approach the problem of finding the number of bridges.

We can run the dfs in the graph problem, and then find the bridges either using the typical low and disc array approach, or by using a dynamic programming approach. Note that I am not a fluent coder in dynamic programming, but the approach discussed out here seemed quite intuitive.

Code for calculating the number of bridges. Link

So we start with two arrays — lvl and dp. The lvl array is for calculating the level of the vertices in the dfs tree. The dp array stores the state for each vertex about the number of edges. Before formally defining the dp, let me approach the recursive solution.

At each level, we have the following tasks —

• Calculate the level of the vertex.
• Calculate the number of back edges in the given level for a given vertex. Actually, the level of the vertex doesn’t matter, we just want to calculate the number of back edges for a given vertex.

The first one is quite simple :P. The second one is a bit complex, so let me break it down as follows -

• We want the number of back-edges for a given vertex. We can start with the leaf vertex, which has no children. Any edge going upwards is counted.
• Also, any back edge that is going downwards is subtracted, as we want only the back edges going upwards.
• We might also need to take care of the number of back edges in a subtree if the vertex is not a leaf vertex. So we add the number of back edges for the subtree.

Now we have a recursive relation for each vertex —

count[v] = #back edges going up + #total back edges in a subtree — #back edges going down.

Here, we can use dynamic programming for using the results computed for the child. Here we might double count the number of back edges for a given vertex, so we can reuse the number of back edges from the child.

So we use the following dp relation —

dp[parent] = #back edges going up + Σdp[childs] — #back edges going down.

Now how to calculate the #back edges going up and down? Fortunately, we can use the lvl array. We have three cases —

• If lvl of the unexplored vertex is NIL, we can initialize the child’s level as 1 + lvl[parent].
• If we encounter a vertex that has been visited, this means we have a back edge, and we need to check if the back edge is going upwards or downwards. If the lvl[parent] > lvl[child], we have a back edge which is going upwards, and we need to add the total back edge by one, or dp[parent] += 1.
• Similarly, if we encounter a vertex that has been visited, this means we have a back edge, and we need to check if the back edge is going upwards or downwards. If the lvl[parent] < lvl[child], we have a back edge which is going downwards, and we need to subtract the total back edge by one, or dp[parent] -= 1.

We also need to subtract the parent-child edge, as we are counting it again.

Concentrate on the second part!

Calculation of Articulation Points

For the calculation of articulation points, we can re-use the dp array. Since dp array represents the number of back-edges for a given vertex, we can use the fact that an articulation point will have no back edge and its descendant subtree will also have no back-edges. So we can insert those vertices in a set of articulation point whose dp[i] = 0along with its parent.

Finally, I have drawn some explanations for the above approach and computed some values for each vertex. The best way to understand them is to draw out and see for yourself. Until then, Ciao Adios!