[Solved]: Split-Find: maintaining dynamic graph connectivity information, under edge deletion

ignougroup
Problem Detail: Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two operations I’d like to be able to perform:

  • Delete$(u,v)$: delete the edge $(u,v)$ from the graph.
  • SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected component

Is there a data structure that allows me to perform both operations relatively efficiently? The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable. However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm. Is there a data structure where both operations can be done in sub-linear running time? One way to think about it is that I am basically asking for the dual of the Union-Find data structure. The Union-Find data structure offers two operations:

  • Union$(u,v)$: add an edge $(u,v)$ to the graph.
  • Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

You could think of this question as asking for a Split-Find data structure, which should support two operations:

  • Split$(u,v)$: delete the edge $(u,v)$ from the graph.
  • Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

As we know, there is an efficient Union-Find data structure. The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too. Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be implemented by calling Split$(u,v)$, and SameComponent$(u,v)$ would be implemented by testing whether Find$(u) = $ Find$(v)$. So, is there an efficient Split-Find data structure?

Asked By : D.W.

Answered By : jbapple

It sounds like you’re looking for “decremental connectivity”. The fastest result I could find was Wulff-Nilson’s “Faster deterministic fully-dynamic graph connectivity”, which “supports updates (edge insertions/deletions) in $O(log^2 n/ log log n)$ amortized time and connectivity queries in $O(log n/ log log n)$ worst-case time, where $n$ is the number of vertices of the graph.”
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32077