3
$\begingroup$

Given a fully connected undirected graph, is there a quick way for me to know if the graph will remain fully connected if I delete a given edge from the graph?

Quick = O(lg V) or something like that. O(V) is not quick.

Fully connected = every node is reachable from every other other node in the graph. i.e., given any two nodes in the graph, there is always a path connecting these two nodes.

$\endgroup$

1 Answer 1

5
$\begingroup$

No, because in the worst case you have to examine every edge (at least, under standard graph representations).

If you can preprocess the graph ($O(|V|+|E|)$ time), you can decompose it into strongly connected components and build a data structure that lets you answer this question in $O(1)$ time.

If you are repeating this many times, alternatively deleting edges and then checking whether deletion will disconnect the graph, see algorithms for decremental graph connectivity.

See also Incremental strongly connected components, Split-Find: maintaining dynamic graph connectivity information, under edge deletion, https://cstheory.stackexchange.com/q/27269/5038.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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