HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Efficiently check if removing an edge splits a strongly connected component

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
efficientlyremovingsplitsedgestronglyconnectedcomponentcheck

Problem

I have a strongly connected component (SCC) of $n$ vertices. Let $n_1n_2$ be an edge between two vertices $n_1$ and $n_2$ in this SCC. Is there an efficient algorithm to check if removing the edge $n_1n_2$ splits the SCC into two SCCs or not? The graph I am using is a directed graph.

Solution

An arc is said to be a bridge if its removal increases the number of connected components of the graph. Further, an arc is a strong bridge if its removal increases the number of strongly connected components. In your case, you are likely interested in finding all strong bridges in a digraph.

A simple $O(n+m)$-time algorithm, where $n$ is the number of vertices and $m$ the number of arcs is given in [1] which identifies all strong bridges. Section 4 of the paper gives the algorithm.

[1] Italiano, Giuseppe F., Luigi Laura, and Federico Santaroni. "Finding strong bridges and strong articulation points in linear time." Theoretical Computer Science 447 (2012): 74-84.

Context

StackExchange Computer Science Q#142502, answer score: 3

Revisions (0)

No revisions yet.