CODEWITHSUNDEEP
algorithmdata-structuresgraph-theory
Thomas
Thomas

Reputation: 181715

Efficient way to check whether a graph has become disconnected?

Using a disjoint set forest, we can efficiently check incrementally whether a graph has become connected while adding edges to it. (Or rather, it allows us to check whether two vertices already belong to the same connected component.) This is useful, for example, in Kruskal's algorithm for computing the minimum spanning tree.

Is there a similarly efficient data structure and algorithm to check whether a graph has become disconnected while removing edges from it?

More formally, I have a connected graph G = (V, E) from which I'm iteratively removing edges one by one. Without loss of generality, let's say these are e_1, e_2, and so on. I want to stop right before G becomes disconnected, so I need a way to check whether the removal of e_i will make the graph disconnected. This can of course be done by removing e_i and then doing a breadth-first or depth-first search from an arbitrary vertex, but this is an O(|E|) operation, making the entire algorithm O(|E|²). I'm hoping there is a faster way by somehow leveraging results from the previous iteration.

I've looked at partition refinement but it doesn't quite solve this problem.

Upvotes: 1

Views: 943

Answers (1)

templatetypedef
templatetypedef

Reputation: 372674

There’s a family of data structures that are designed to support queries of the form “add an edge between two nodes,” “delete an edge between two nodes,” and “is there a path from node x to node y?” This is called the dynamic connectivity problem and there are many data structures that you can use to solve it. Unfortunately, these data structures tend to be much more complicated than a disjoint-set forest, so you may want to search around to see if you can find a ready-made implementation somewhere.

The layered forest structure of Holm et al works by maintaining a hierarchy of spanning forests for the graph and doing some clever bookkeeping with edges to avoid rescanning them when seeing if two parts of the graph are still linked. It supports adding and deleting edges in amortized time O(log2 n) and queries of the form “are these two nodes connected?” in time O(log n / log log n).

A more recent randomized structure called the randomized cutset was developed by Kapron et al. It has worst-case O(log5 n) costs for all three operations (IIRC).

There might be a better way to solve your particular problem that doesn’t require these heavyweight approaches, but I figured I’d mention these in case they’re helpful.

Upvotes: 2

Related Questions