Graph is at the base of many applications, namely networking, navigation system, recommender system etc. However, in most cases, for a graph to be stable for the given application should be devoid of articulation points and bridges.


Before understanding how to find them and why they can be an issue, let us first get familiar with some terminologies.

Connected Components

In graph theory, a connected component is a group of vertices such that there exists a path between any two vertex in the group and the group of vertices along with their incoming and outgoing edges are isolated from the other leftover graph.

Articulation Point

In graph theory, an articulation point is any vertex whose removal, along with incoming and outgoing edges associated with it, from the graph increases the number of connected components in the graph.

Lets see an example to understand the concept of articulation point more clearly.

Graph with 5 vertices

The graph above has two articulation points, namely 3,

Graph with vertex 3 removed

and 4,

Graph with vertex 4 removed

Bridge

In graph theory, a bridge is an edge whose removal from the graph increases the number of connected components.

For example, for the above graph we have two bridges which are emphasised with a red colour.

DFS Tree

Depth First Search traversal of a graph produces a spanning tree of the graph. This spanning tree of the graph is called the DFS tree of the graph.

For example for the above graph, the DFS Tree will be

DFS Tree for the above Graph

Back Edge

In a DFS tree, back edge is an edge that connects a vertex to an already discovered vertex in the DFS tree.

In the above diagram, the highlighted edge is a back edge.


Finding Articulation Points

Naive Approach

The most simplest approach to find articulation points is to remove every vertex one-by-one and to count the number of components in the remaining graph.

Pseudo Code :

dfs(node, visited, graph)
    visited[node]=true
    for child in graph[node]
    	if visited[child]!=true
            dfs(child, visited, graph)

countComponents(V, visited, graph)
    nComponents=0
    for i=1 to V
        if visited[i]!=true
            nComponents++
            dfs(i, visited, graph)
    return nComponents

findArticulationPoints(V, graph)
    isArticulationPoints={false}
    visited[V]={false}
    initialComponents=countComponents(V, visited, graph)
    for i=1 to V
        for j=1 to V
            visited[j]=false
            copy[j]=graph[i][j]
            graph[i][j]=graph[j][i]=0
        nComponents=countComponents(V, visited, graph)
        if(nComponents>initialComponents)
        	isArticulationPoint[i]=true
        for j=1 to V
        	graph[i][j]=graph[j][i]=copy[j]

Time Complexity : O(V*(V+E))

Can we do something better than this?

Efficient Approach

We use the DFS tree to find the articulation point. The main point to note here is that a vertex can be an articulation point if and only if, the vertex :

  1. is the root of the tree and has more than 1 child.
  2. has a sub-tree in which no vertex has a back edge to a vertex in (sub-tree)c of the DFS tree.

Let us look more carefully at the above two points.

If the the vertex of the root of the tree and has more than one child, then removal of the root breaks the tree into sub-components and hence, in the graph there is no possible path from the first component to the second component.

If the sub-tree rooted at vertex V' has a back-edge to a vertex in (sub-tree)c then after the removal of the vertex V' there still exists a path from the other part of the DFS tree to the sub-tree through the back-edge. Hence, there still exists a path from every vertex to every other vertex in the graph. Therefore, for vertex V' to be an articulation point there should be no back-edge from the sub-tree to the other part of the tree.

Algorithm

In the algorithm, to get a hold of positions of the vertices in the DFS tree and back-edges, we use two flags namely,

  1. disc: keeps a track of the discovery time of the vertex
  2. low: keeps a track of the lowest discovered vertex (except the parent vertex) that can be reached by that vertex in the tree

We also use a visited and nChildren flag to check if a vertex has already been discovered and to count the number of children respectively.

We use a Depth First Traversal (DFS) to form the DFS Tree. At each vertex V we traverse the list of vertices that have an edge from the vertex V.

  1. For every discovered or visited vertex V' (except the parent), we update low[V] to be min(disc[V'], low[V]).
  2. For each undiscovered or not-visited vertex V', we recursively traverse the edges through V' and then update low[V] to be min(low[V'], low[V]). We also check if V is an articulation point by using the condition, is low[V'] greater than or equal to disc[V]?.
  3. If V is the root of the DFS Tree, we also check for the number of children.

Pseudo Code :

visited[v]={false}
isArticulationPoint[V]={false}
disc[V], low[V]
parent[V]={noParent}
time=0

dfs(vertex)
    visited[vertex]=true
    disc[vertex]=low[vertex]=time+1
    time++
    nChildren=0
    for child in graph[vertex]
        if child==parent[vertex]
            continue
        else if visited[child]==false
            nChildren++
            parent[child]=vertex
            dfs(child)
     	    // Checking for child's back-edge
            low[vertex]=min(low[vertex], low[child])
            if parent[vertex]==noParent and nChildren>1
    	        isArticulationPoint[vertex]=true
            if parent[vertex]!=noParent and low[child]>=disc[vertex]
                isArticulationPoint[vertex]=true
        else
            // Checking for back-edge
        	low[vertex]=min(low[vertex], disc[vertex])

Time Complexity : O(V+E)


Finding Bridges

Naive Algorithm

The most simplest approach to find bridges is to remove every edge one-by-one and to count the number of components in the remaining graph.

Pseudo Code :

dfs(node, visited, graph)
    visited[node]=true
    for i=0 upto graph[node].length
    	if graph[node][i].edge==true
        	continue
        child=graph[node][i]
    	if visited[child]!=true
            dfs(child, visited, graph)

countComponents(V, visited, graph)
    nComponents=0
    for i=1 to V
        if visited[i]!=true
            nComponents++
            dfs(i, visited, graph)
    return nComponents

findBridges(V, edges, graph)
    E=edges.length
    isBridge[E]={false}
    visited[V]={false}
    initialComponents=countComponents(V, visited, graph)
    for i=0 upto E
    	visited[V]={false}
        u, w=edges[i]
        graph[u][w].edge=graph[w][u].edge=true
        nComponents=countComponents(V, visited, graph)
        if(nComponents>initialComponents)
        	isBridge[i]=true
        graph[u][w].edge=graph[w][u].edge=false

Time Complexity : O(E*(V+E))

Efficient Approach

The approach here is similar to the approach given above for articulation points. The only change here is in the condition for which an edge is a bridge i.e. an edge connecting vertex V and V' (where V is the parent of V') is a bridge if and only if the sub-tree rooted at V' has no vertex which has a back edge to (sub-tree)c U {V}.

Pseudo Code :

visited[v]={false}
isBridge[E]={false}
disc[V], low[V]
parent[V]={noParent}
time=0

dfs(vertex)
    visited[vertex]=true
    disc[vertex]=low[vertex]=time+1
    time++
    for child in graph[vertex]
        if child==parent[vertex]
            continue
        else if visited[child]==false
            parent[child]=vertex
            dfs(child,vertex)
     	    // Checking for child's back-edge
            low[vertex]=min(low[vertex], low[child])
            if low[child]>disc[vertex]
                isBridge[(vertex<->child).id]=true
        else
            // Checking for back-edge
                low[vertex]=min(low[vertex], disc[vertex])

Time Complexity : O(V+E)


Issue with Articulation Point and Bridges

In graphs, articulation points and bridges are often the chink in one's armour. These vertices and edges are single points of failure in the system and often make the system highly vulnerable to malicious attackers leading to instability in the system. Failure at articulation points and bridges splits up the system which may be highly undesirable depending on the application of the system. Hence detecting articulation points and bridges and getting rid of them is often a very important step towards stability in graph-based models.