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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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)$.
-
$\begingroup$ Note that this can be costly in practice if the goal is to identify all such arcs. $\endgroup$– JuhoCommented Jul 21, 2021 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$– ErroRCommented Jul 21, 2021 at 7:54