DS & Algo Problems — Bridges and Articulation Points
In this post we are going to look at a problem that is very relevant from a network analysis point of view. In a circuit network of wires, we would like to identify vulnerable connections that could be a single point of failure. Single point of failures like these are known as Articulation Points.
In a social network we would like to identify people who sits at the vulnerable points and hold together multiple sub-networks. Targeting these people for marketing offers and promotions and preventing them from churning will ensure that the network is still connected. In a terrorist network, we would like to eliminate such articulation points.
By definition an Articulation Point in a graph is a node which when removed (along with the edges connecting it) increases the number of connected components. A Bridge is an edge in a graph which when removed increases the number of connected components.
For e.g. in the graph below:
The nodes 0 and 1 are Articulation Points because removing the node 1, will create two connected components i.e. will break the graph.
Brute force approach to finding the articulation points is to remove each node and then check if the number of connected components has increased or not. If the number of nodes is V and number of edges is E, then time complexity of the brute force approach is O(V*(V+E)).
Python program to return all articulation points.
‘graph’ is an adjacency list. For the above example:
graph[0] = [1, 5]
graph[1] = [0, 2, 3]
graph[2] = [1, 3, 4]
graph[3] = [1, 2, 4]
graph[4] = [2, 3]
graph[5] = [0]
For each node, do a BFS traversal (excluding the node and all edges connecting the node) to find the number of connected components.
Similarly we can do brute force to find the Bridges by removing each edge and counting the number of connected components. Run-time complexity is O(E*(V+E)).
We can improve the run-time by observing that while doing DFS starting from a root node X, if we encounter a node U such that for all children V of U if there is an edge (‘back-edge’) from any node in the DFS sub-tree rooted at V to an ancestor of U, then even if we delete U, we can always reach the node V through the back-edge. But if for at-least one child V of U, there is no back-edge from a successor node of V to an ancestor of U, then deleting U will disconnect V from the ancestors of U. Thus U is an articulation point in this case.
For root node X, since there is no ancestor, it is an articulation point if there are more than one child node in the DFS tree.
An edge A-B is a back edge in the DFS traversal, if we discovered B from A by traversing along a path with multiple vertices A — — — C — — — B, but actually we could have reached B from A directly through another path. Thus A-B is a back-edge in the DFS tree if depth of A is less than depth of C.
Thus if we denote P[v] as the depth of node ‘v’ in the DFS traversal. Let Q[v] denote the following:
Q[v] = minimum(P[v], min(P[u]|for all u), min(Q[w]|for all w))
where u-v is a back edge and ‘w’ is a child node of ‘v’ in the DFS tree.
Q[v] is the minimum of the depth of node ‘v’, the minimum depth of any node ‘u’ connecting ‘v’ through back-edge and Q[w] for all child ‘w’ of ‘v’.
Then U is an articulation point if for any child V of U:
Q[V] ≥ P[U] i.e. all nodes in the subtree rooted at V has been discovered later than U (i.e. Q[V] > P[U]) or there is a node which has a back edge to U (i.e. Q[V] = P[U]), implying deleting U will disconnect V and its subtree from U’s ancestors.
For finding bridges, the edge U-V is a bridge if Q[V] > P[U].
For more in-depth discussions, refer to the following articles:
- https://cp-algorithms.com/graph/cutpoints.html
- https://codeforces.com/blog/entry/71146
- https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/
Below is the Python implementation for finding Articulation Points and Bridges using the above algorithm:
Time complexity of the above approach is O(V+E).
Lets look at 2 problems to see how to tackle them using Bridge Finding and Articulation Points algorithms.
Problem 1:
There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
The problem requires finding bridges in the network.
Python solution:
Convert the edges into adjacency list and then using above approach find the bridges in the graph.
Problem 2:
You are a social gaming platform ‘Bazinga’ with millions of users. Games being multiplayer, different players from varied backgrounds come to your platform to play your most engaging game called the ‘SharkVille’.
But recently you observed that many players are churning from the game due to various reasons such as insufficient game coins, lack of coordination among players, no offers etc.
You are responsible for building a churn prediction model but you are not that familiar with Machine Learning techniques to build such a model. But you were quite good in Graph Theory in your class. Using graph theory you observed that there are certain networks of gamers which has widely varying backgrounds such as musicians and PhDs, but among them there are certain gamers who were both i.e. a PhD holder who is fond of music. Once these guys start to churn, the musicians and PhDs feels like they are total strangers to the other group and thus begin to churn themselves.
Can you find these people with multiple skills that sits in between different networks and provide them with offers and promotions such that they do not churn ?
This can be solved using Articulation Point algorithm. Observe that people with multiple skills i.e. PhD holder who is fond of music are the articulation points and allowing them to churn will break the network into multiple sub-networks.
Few other problems found on various sites dealing with Bridges and Articulation Points:
Finding Bridges or Articulation Points is not trivial if someone is not aware of the above algorithm. I personally like this problem because it can be easily applied to practical scenarios such as social settings, telephone networks, roadways etc.
