How to detect if breaking an edge will make a graph disjoint?

Question

I have a graph that starts off with a single, root node. Nodes are added one by one to the graph. At node creation time, they have to be linked either to the root node, or to another node, by a single edge. Edges can also be created and deleted (one by one, between any two nodes). Nodes can be deleted one at a time. Node and edge creation, deletion operations can happen in any arbitrary order.

OK, so here's my question: When an edge is deleted, is it possible do determine, in constant time (i.e. with an O(1) algorithm), if doing this will divide the graph into two disjoint subgraphs? If it will, then which side of the edge will the root node belong?

I'm willing to maintain, within reasonable limits, any additional data structure that can facilitate the derivation of this information.

Maybe it is not possible to do it in O(1), if so any pointers to literature will be appreciated.

Edit: The graph is a directed graph.

Edit 2: OK, maybe I can restrict the case to deletion of edges from the root node. [Edit 3: not, actually] Also, no edge lands into the root node.

Answer 1

Is this a directed graph? The below assumes undirected.

What you are looking for is whether the given edge is a Bridge in the graph. I believe this can be found using a traversal looking for cycles containing that edge and would be O(|V| + |E|).

O(1) is too much to ask.

You might find that looking to maintain 2-edge connected components in dynamic graphs could be useful to you.

Eppstein et al have a paper on this: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

which can maintain 2-edge connected components, in a graph of n nodes where edge insertions and deletions are allowed. It has O(sqrt(n)) time per update and O(log n) time per query.

So any time you delete, you can query in O(logn) to determine if the number of 2-edge connected components has changed. I suppose it can also tell you which component a specific node is in.

This paper is more general and applies to other graph problems, not only 2 edge connected components.

I suggest you look for bridges and dynamic 2-edge connectivity to get you started.

Hope that helps.

Answer 2

To speed things up a little over the obvious O(|V|+|E|) solution, you could keep a spanning tree which is fairly easy to update as the graph is changed.

If an edge not in the spanning tree is deleted, then the graph isn't disconnected and do nothing. If an edge in the spanning tree is deleted, then you must try to find a new path between those two vertices (if you find one, use it to update the spanning tree, otherwise the graph is disconnected).

So, best case O(1), worst-case O(|V|+|E|), but fairly simple to implement anyway.

Answer 3

Hello there, as said by Moron just before, you are actually looking for a Bridge in your graph.

Now a Bridge is an edge that has the described attribute and also originates and ends up in Cut Vertexes. Cut vertex is exactly what a Bridge is, but in a vertex (node) edition.

So the only way (though quite bending the initial data structure hypothesis) I can think of, to get a O(1) complexity for this, is if you first check every node in your graph if it is a Cut Vertex and then simply in constant time checking if the edge you want to delete is a attached to one of those two.

Finding if a node in a graph is a Cut Vertex takes O(m+n) where m = # edges and n= # nodes.

Cheers