2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Yes, there is a linear time algorithm. After removing $e=(n_1,n_2)$ we run DFS twice as follow

First, run DFS from $n_1$ and check, $n_2$ reachable from $n_1$ or not.

Second, run DFS from $n_2$ and check whether $n_1$ reachable from $n_2$ or not.

If after running DFS twice, $n_1$ reachable from $n_2$ and $n_2$ reachable from $n_1$ we conclude that removing edge $e=(n_1,n_2)$ can't change our SCC, but otherwise SCC changed and number of SCC has increased that you can compute SCC again from scratch in linear time. So the running time of DFS is linear and finding SCC is linear, total time is $\mathcal{O}(E+V)$.

$\endgroup$
2
  • $\begingroup$ Note that this can be costly in practice if the goal is to identify all such arcs. $\endgroup$
    – Juho
    Jul 21 at 7:03
  • $\begingroup$ Yes, i know that it's costly, if we remove multiple edges, but the question is about one edge. On the other hand we can't do better than linear time in that problem. $\endgroup$
    – Jut
    Jul 21 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.