I have a simple connected undirected graph $G=(V, E)$ and I would like to enumerate all possible connected components that arise from removing $k$ edges in $E$. A naive way is to remove each $k$-tuple of edges (of which there are $\binom{|E|}{k}$ total) and then run a connected components algorithm, but this feels incredibly wasteful. I know there are dynamic decremental connectivity algorithms but these appear optimized for on-line (dynamic) use, which again seems wasteful.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
You might be optimizing on the wrong end. Finding connected components for a fixed graph can be done in $O(|V|+|E|)$ time. With the dynamic decremental algorithm you link to, you can reduce that to $O(|V|)$. And you still consider it wasteful.
My primary concern would be the number ${|E|}\choose k$ which, contrary to all the above, is not polynomial in the input. One observation that might help here: If you can identify an $l$-edge-connected subgraph, then you only need to consider $k$-tuples of edges that have either at least $l$ edges from the subgraph or none at all.
-
$\begingroup$ I agree that the $\binom{|E|}{k}$ is the more concerning part, I was hoping there might be an algorithm that would let me further amortize the deletions of the dynamic decremental approaches (since I'm doing all of them). I'm somewhat familiar with data structures like SQPR trees which I think could be adapted to solve my problem for $k=2$ but I have been unsuccessful in finding generalizations to higher values of $k$. $\endgroup$– Eric JJul 5, 2021 at 21:03