Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
