6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ A very nice question! I have been thinking about the exact same question myself. It has many applications in divide and conquer graph algorithms. $\endgroup$
    – Pål GD
    Mar 10, 2015 at 22:16
  • $\begingroup$ Closely related. $\endgroup$
    – Raphael ♦
    Oct 11, 2016 at 6:46

2 Answers 2

Reset to default
5
$\begingroup$

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."

Improve this answer
$\endgroup$
1
0
$\begingroup$

Here is (the earliest?) ref I know of. It includes data structure motivation and details: https://www.cs.duke.edu/~reif/paper/topdyncon.pdf

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Thanks, this looks very helpful! However, link-only answers are generally discouraged on this site, partly because links rot and then a link-only answer becomes useful, and partly because we want to add new value. Could you edit your answer to add a short summary of the result (e.g., the running time of the data structure, maybe its main idea)? Also can you add a full citation to the paper (title, authors, where published) so that if the link stops working so that if the link to the PDF stops working we can still find which paper you were referring to? Thank you! $\endgroup$
    – D.W. ♦
    Apr 23, 2015 at 21:32

Your Answer

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

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