Find cut edges in a graph

• Algorithm
• Complexity
• Pseudocode
• Applications
• Discussions

Reading time: 15 minutes | Coding time: 12 minutes

A cut edge e = uv is an edge whose removal disconnects u from v.
Clearly such edges can be found in O(m^2) time by trying to remove all edges in the graph. We can get to O(m) based on the following two observations:

1. All cut edges must belong to the DFS tree.
2. A tree edge uv with u as v’s parent is a cut edge if and only if there are no edges in v’s subtree that goes to u or higher.

Strategy

We need compute for each subtree, the lowest node in the DFS tree that a back edge can reach. This value can either be the depth of the other end point, or the discovery time. Hint: Depth First Search

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]
                                then the edge v-u is a cut edge
                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).

Applications

• Cut edge denotes a critical edge that when removed, splits the graph into two components. It has real-world applications in the relation that cut edges may denote roads that need regular maintainence to ensure smooth traffic flow within an area.

• Cut edges can, also, be seen as edges that needs to be removed to end up with strongly connected components.