Cut Points Search

• Input: undirected graph with N nodes and M edges
• Output: array cutpoints of graph cut points
• Time complexity: $O(N + M)$

Cut point - is a node of a graph whose deletion increases the graph's number of connected components

Description

Pick an arbitrary node as source_node and run depth first search from it.

Let's say we are in the DFS, looking through the edges starting from node u $\neq$ source_node. If the current edge (u, v) is such that none of the nodes v or its descendants in the DFS traversal tree has a back-edge to any of ancestors of u, then u is a cut point. Otherwise, u is not a cut point.

Let's consider the remaining case of u $=$ source_node. This node will be a cut point if and only if this node has more than one child in the DFS traversal tree.

Let entry_time[u] denote DFS entry time for node u.

Let lowpoint[u] denote the lowest entry time of neighbors of all descendants of u (including u itself) in the DFS tree.

$$ \operatorname{lowpoint[u]} = \operatorname{min} \begin{cases} \operatorname{entry\_time[u]}\\ \operatorname{entry\_time[p]} & \forall \text{ back-edge } (u, p)\\ \operatorname{lowpoint[v]} & \forall \text{ DFS edge } (u, v) \end{cases} $$

Now, there is a back edge from node u or one of its descendants to one of its ancestors if and only if node u has a child v for which lowpoint[v] $<$ entry_time[u]. If lowpoint[v] = entry_time[u], the back edge comes directly to u, otherwise it comes to one of the ancestors of u.

Thus, the current node u in the DFS tree is a cut point if and only if lowpoint[v] $\geq$ entry_time[u].

Example

Let's see how the Cut Points Search algorithm works with an example. We use an undirected graph with 7 nodes.

Cut Points Search algorithm starts from node 1 and set visited[1] = 1, entry_time[1] = 0, lowpoint[1] = 0, timer = 1.

Cut Points Search moves to node 2 and set visited[2] = 1, entry_time[2] = 1, lowpoint[2] = 1, timer = 2.

Cut Points Search moves to node 3 and set visited[3] = 1, entry_time[3] = 2, lowpoint[3] = 2, timer = 3.

Cut Points Search moves to node 4 and set visited[4] = 1, entry_time[4] = 3, lowpoint[4] = 3, timer = 4.

Cut Points Search moves to node 7 and set visited[7] = 1, entry_time[7] = 4, lowpoint[7] = 4, timer = 5.

Cut Points Search backtrack from node 7 to node 4. Since lowpoint[7] = 4 $\geq$ 3 = entry_time[4], Cut Points Search marks node 4 as a cut point.

Considering edge (4, 1) Cut Points Search update lowpoint[4] = 0.

Cut Points Search backtrack from node 4 to node 3 and set lowpoint[3] = 0.

Cut Points Search moves to node 6 and set visited[6] = 1, entry_time[6] = 5, lowpoint[6] = 5, timer = 6.

Cut Points Search backtrack from node 6 to node 3. Since lowpoint[6] = 5 $\geq$ 2 = entry_time[3], Cut Points Search marks node 3 as a cut point.

Cut Points Search backtrack from node 3 to node 2 and set lowpoint[2] = 0.

Cut Points Search moves to node 5 and set visited[5] = 1, entry_time[5] = 6, lowpoint[5] = 6, timer = 7.

Cut Points Search backtrack from node 5 to node 2. Since lowpoint[5] = 6 $\geq$ 1 = entry_time[2], Cut Points Search marks node 2 as a cut point.

Cut Points Search backtrack from node 2 to node 1 without updating anything.

Cut Points Search finished at node 1.

Code

                        def cutpoints_search(graph: Dict[int, List[int]]) -> List[Tuple[int, int]]:
                            n = len(graph)
                            visited = [False] * n
                            entry_time = [-1] * n
                            lowpoint = [-1] * n
                            timer = 0
                        
                            cutpoints = []
                        
                            def dfs(node: int, parent: int = -1):
                                nonlocal visited, entry_time, lowpoint, timer, cutpoints
                                visited[node] = True
                                entry_time[node] = timer
                                lowpoint[node] = timer
                                timer += 1
                        
                                children_count = 0
                                for neighbour in graph[node]:
                                    if neighbour == parent:
                                        continue
                        
                                    if visited[neighbour]:
                                        lowpoint[node] = min(
                                            lowpoint[node],
                                            entry_time[neighbour],
                                        )
                                    else:
                                        dfs(neighbour, parent=node)
                                        lowpoint[node] = min(
                                            lowpoint[node],
                                            lowpoint[neighbour],
                                        )
                                        if lowpoint[neighbour] >= entry_time[node] and -1 != parent:
                                            cutpoints.append(node)
                                        children_count += 1
                                if -1 == parent and children_count > 1:
                                    cutpoints.append(node)
                        
                            for node in range(len(graph)):
                                if False == visited[node]:
                                    dfs(node)
                        
                            return cutpoints