Understanding Articulation Points and Bridges

Originally published at Seedbx.com on September 18, 2020.

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.

The graph above has two articulation points, namely 3,

and 4,

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

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

Pseudo Code :

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.

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]

Can we do something better than this?

Efficient Approach

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.

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 :

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.

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 :

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.

Time Complexity : O(V+E)

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 low[child]>=disc[vertex]
                isArticulationPoint[child]=true
        else
            // Checking for back-edge
         low[vertex]=min(low[vertex], disc[vertex])
    if parent[vertex]==noParent and nChildren>1
     isArticulationPoint[vertex]=true

Finding Bridges

Naive Algorithm

Pseudo Code :

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.

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

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

Efficient Approach

Pseudo Code :

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}.

Time Complexity : O(V+E)

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])

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.

Thanks for reading the article!

Leave a comment below if you have any questions. Be sure to leave a clap if you like the article.

Originally published at Seedbx.com on September 18, 2020.