Explanation of Algorithm for finding articulation points or cut vertices of a graph

Question

I have searched the net and could not find any explanation of a DFS algorithm for finding all articulation vertices of a graph. There is not even a wiki page.

From reading around, I got to know the basic facts from here. PDF

There is a variable at each node which is actually looking at back edges and finding the closest and upmost node towards the root node. After processing all edges it would be found.

But I do not understand how to find this down & up variable at each node during the execution of DFS. What is this variable doing exactly?

Please explain the algorithm.

Thanks.

Answer 1

Finding articulation vertices is an application of DFS.

In a nutshell,

1. Apply DFS on a graph. Get the DFS tree.
2. A node which is visited earlier is a "parent" of those nodes which are reached by it and visited later.
3. If any child of a node does not have a path to any of the ancestors of its parent, it means that removing this node would make this child disjoint from the graph.
4. There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.

Point 3 essentially means that this node is an articulation point.

Now for a child, this path to the ancestors of the node would be through a back-edge from it or from any of its children.

All this is explained beautifully in this PDF.

Answer 2

I'll try to develop an intuitive understanding on how this algorithm works and also give commented pseudocode that outputs Bi-Components as well as bridges.

It's actually easy to develop a brute force algorithm for articulation points. Just take out a vertex, and run BFS or DFS on a graph. If it remains connected, then the vertex is not an articulation point, otherwise it is. This will run in O(V(E+V)) = O(EV) time. The challenge is how to do this in linear time (i.e. O(E+V)).

Articulation points connect two (or more) subgraphs. This means there are no edges from one subgraph to another. So imagine you are within one of these subgraphs and visiting its node. As you visit the node, you flag it and then move on to the next unflagged node using some available edge. While you are doing this, how do you know you are within still same subgraph? The insight here is that if you are within the same subgraph, you will eventually see a flagged node through an edge while visiting an unflagged node. This is called a back edge and indicates that you have a cycle. As soon as you find a back edge, you can be confident that all the nodes through that flagged node to the one you are visiting right now are all part of the same subgraph and there are no articulation points in between. If you didn't see any back edges then all the nodes you visited so far are all articulation points.

So we need an algorithm that visits vertices and marks all points between the target of back edges as currently-being-visited nodes as within the same subgraph. There may obviously be subgraphs within subgraphs so we need to select largest subgraph we have so far. These subgraphs are called Bi-Components. We can implement this algorithm by assigning each bi-component an ID which is initialized as just a count of the number of vertices we have visited so far. Later as we find back edges, we can reset the bi-compinent ID to lowest we have found so far.

We obviously need two passes. In the first pass, we want to figure out which vertex we can see from each vertex through back edges, if any. In the second pass we want to visit vertices in the opposite direction and collect the minimum bi-component ID (i.e. earliest ancestor accessible from any descendants). DFS naturally fits here. In DFS we go down first and then come back up so both of the above passes can be done in a single DFS traversal.

Now without further ado, here's the pseudocode:

time = 0
visited[i] = false for all i
GetArticulationPoints(u)
    visited[u] = true
    u.st = time++
    u.low = v.st    //keeps track of highest ancestor reachable from any descendants
    dfsChild = 0    //needed because if no child then removing this node doesn't decompose graph
    for each ni in adj[i]
        if not visited[ni]
            GetArticulationPoints(ni)
            ++dfsChild
            parents[ni] = u
            u.low = Min(u.low, ni.low)  //while coming back up, get the lowest reachable ancestor from descendants
        else if ni <> parent[u] //while going down, note down the back edges
            u.low = Min(u.low, ni.st)

    //For dfs root node, we can't mark it as articulation point because 
    //disconnecting it may not decompose graph. So we have extra check just for root node.
    if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
        Output u as articulation point
        Output edges of u with v.low >= u.low as bridges
    output u.low as bicomponent ID

Answer 3

One fact that seems to be left out of all the explanations:

Fact #1: In a depth first search spanning tree (DFSST), every backedge connects a vertex to one of its ancestors.

This is essential for the algorithm to work, it is why an arbitrary spanning tree won't work for the algorithm. It is also the reason why the root is an articulation point iff it has more than 1 child: there cannot be a backedge between the subtrees rooted at the children of the spanning tree's root.

A proof of the statement is, let (u, v) be a backedge where u is not an ancestor of v, and (WLOG) u is visited before v in the DFS. Let p be the deepest ancestor of both u and v. Then the DFS would have to visit p, then u, then somehow revisit p again before visiting v. But it isn't possible to revisit p before visiting v because there is an edge between u and v.

---

Call V(c) the set of vertices in the subtree rooted at c in the DFSST
Call N(c) the set of vertices for which that have a neighbor in V(c) (by edge or by backedge)

Fact #2:

For a non root node u,
If u has a child c such that N(c) ⊆ V(c) ∪ {u} then u is an articulation point.

Reason: for every vertex w in V(c), every path from the root to w must contain u. If not, such a path would have to contain a back edge that connects an ancestor of u to a descendant of u due to Fact #1, making N(c) larger than V(c).

Fact #3:

The converse of fact #2 is also true.

Reason: Every descendant of u has a path to the root that doesn't pass through u. A descendant in V(c) can bypass u with a path through a backedge that connects V(c) to N(c)/V(c).

---

So for the algorithm, you only need to know 2 things about each non-root vertex u:

1. The depth of the vertex, say D(u)
2. The minimum depth of N(u), also called the lowpoint, lets say L(u)

So if a vertex u has a child c, and L(c) is less than D(u), then that mean the subtree rooted at c has a backedge that reaches out to an ancestor of u which makes it not an articulation point by Fact #3. Conversely also by Fact #2.

Answer 4

If low of the descendant of u is greater than the dfsnum of u, then u is said to be the Articulation Point.

int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];

void cutvertex(int u){
    low[u]=dfsnum[u]=num++;
    for (int v = 0; v < 256; ++v)
    {
        if(adjMatrix[u][v] && dfsnum[v]==-1)
        {
            cutvertex(v);
            if(low[v]>dfsnum[u])    
                cout<<"Cut Vertex: "<<u<<"\n";
            low[u]=min(low[u], low[v]);
        }
        else{
            low[u]=min(low[u], dfsnum[v]);
        }
    }
}