Find articulation points or cut vertices in a graph

• Algorithm
• Complexity
• Pseudocode
• Implementation
• Applications
• Discussions

Reading time: 15 minutes | Coding time: 12 minutes

A vertex in an undirected connected graph is an articulation point or cut vertex if and only if removing it, and the edges connected to it, splits the graph into multiple components.

Hint: Apply Depth First Search on a graph.

• Construct the DFS tree.
• A node which is visited earlier is a "parent" of those nodes which are reached by it and visited later.
• 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. This means that this node is an articulation point.
• There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.

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.

Complexity

• Worst case time complexity: Θ(V+E)
• Average case time complexity: Θ(V+E)
• Best case time complexity: Θ(V+E)
• Space complexity: Θ(V)

Pseudocode

h[root] = 0
par[v] = -1
dfs (v):
        d[v] = h[v]
        color[v] = gray
        for u in adj[v]:
                if color[u] == white
                        then par[u] = v and dfs(u) and d[v] = min(d[v], d[u])
                        if d[u] >= h[v] and (v != root or number_of_children(v) > 1)
                                then the edge v is a cut vertex
                else if u != par[v])
                        then d[v] = min(d[v], h[u])
        color[v] = black
 

where h[v] =  height of vertex v in the DFS tree and d[v] = min(h[w] where there is at least vertex u in subtree of v in the DFS tree where there is an edge between u and w).

Implementation

• C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;
// Part of Cosmos by OpenGenus Foundation
const int MAXN = 1e4+5;
vector<int> adj[MAXN];
bool vis[MAXN], AP[MAXN];
int n, m, currTime, disc[MAXN];
int low[MAXN];  // low[i] is the minimum of visited currTime of all vertices which are reachable from i.
void init(){
    currTime = 0;
    for(int i = 1;i <= n; i++){adj[i].clear();vis[i]=false;AP[i]=false;disc[i]=0;low[i]=INT_MAX;}
}
void dfs(int u, int parent){
    vis[u] = true;
    disc[u] = low[u] = currTime+1;
    int child = 0;
    for(auto v : adj[u]){
        if(v == parent)     continue;
        if(!vis[v]){
            child = child+1;
            currTime++;
            dfs(v, u);
            //check if subtree rooted at v has a connection to one of the ancestors of u.
            low[u] = min(low[u], low[v]);
            if(parent == -1 && child > 1)
                AP[u] = true;          
            if(parent != -1 && low[v] >= disc[u])
                AP[u] = true;
        }else{
            // back edge.
            low[u] = min(low[u], disc[v]);
        }
    }
}
int main(){
    cin >> n >> m;  // n = number of vertices, m = number of edges
    init();
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, -1); //start from any random vertex, make its parent -1.   
    return 0;
}

Applications

• Cut vertices denote the vertices that are critical in keeping the graph connected. Removing the vertex results in splitting of the graph.

• Think of a cut vertex as a person who keeps five communities connected. The person may be a motivational activist. If this person is taken off consideration, then the five different communities become separate and hence, is detrimental as it results in discrimination. Thus, the person (cut vertex) is very important and must be supported.