12
$\begingroup$

Problem

I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected components of this graph.

Properties

Additional properties are that no two components will ever be reconnected. Obviously, the graph can have cycles to an arbitrary amount (otherwise the solution would be trivial). If an edge $e$ does not contain a node $n$, it will never adopt that node. However, if $n \in e$, it can change to $n \notin e$.

Approaches

I have two possible approaches so far, but as you will see they are horrible:

Slow state-less

I can search (dfs/bfs) the graph starting from the modified element(s) every time. This conserves space, but is slow as we have O(n+m) for each modification.

Stateful fast(-er) (?) approach

I can store all possible paths for each node to all possible nodes, but if I see it correctly, this will take O(n^4) memory. But I am not sure how the runtime improvement is (if there is one at all, because I have to keep the information up-to-day for every node in the same component).

Question

Do you have any pointers, how I can learn more about that problem or perhaps some algorithms I can build on?

Note

If there is a vast improvement in runtime/memory I could live with a non-optimal solution that sometimes says two components are one, but of course I would prefer an optimal solution.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ If I read your last two sentences in "Properties" right, then it seems that you are interested in the decremental problem only. If so, be sure to check out Thorup's work on decremental dynamic connectivity. (You can find the citation via JeffE's pointers, which are for the fully dynamic version of the problem.) $\endgroup$ – Maverick Woo Oct 30 '10 at 2:36
  • $\begingroup$ @Maverick Woo: There can always be new edges/nodes. I think the last property is not very strong, for exactly this reason. Does it still qualify as decremental? $\endgroup$ – bitmask Oct 30 '10 at 7:05
  • $\begingroup$ Oops, I don't know how I missed the very first sentence... See the "answer" below. $\endgroup$ – Maverick Woo Oct 30 '10 at 12:57
17
$\begingroup$

There are several data structures that support edge insertions, edge deletions, and connectivity queries (Are these two vertices in the same connected component?) in polylogarithmic time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This sounds awesome, once I'm through the papers, I'll most likely accept this. $\endgroup$ – bitmask Oct 29 '10 at 22:20
6
$\begingroup$

I think that you are looking for what is called the dynamic graph algorithm for connected component decomposition. The algorithm by Holm, de Lichtenberg and Thorup [HLT01] has amortized polylogarithmic time on each edge update. It has been long since I looked at the problem last time, so there is probably more recent progress.

[HLT01] Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723–760, July 2001. http://doi.acm.org/10.1145/502090.502095

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Jinx. You owe me a coke. $\endgroup$ – Jeffε Oct 29 '10 at 21:38
  • $\begingroup$ @JeffE: I did not know about that game. But according to the rules, I have not lost the game (I am just in the “jinxed” state), so I do not owe you a coke unless I speak further… oh, wait a moment. $\endgroup$ – Tsuyoshi Ito Oct 29 '10 at 21:48
  • $\begingroup$ if only you could trade in reputation points :) $\endgroup$ – Suresh Venkat Oct 29 '10 at 21:58
5
$\begingroup$

(For now let me just stick with connectivity queries, which unfortunately may not be sufficient for your application.)

Many of the previous work on the dynamic connectivity problem is in the edge-update model: you assume the number of vertices is fixed, and you can insert and/or delete edges while making queries. If you can only insert (delete), that's incremental (decremental). If you can do both, that's fully-dynamic. Thorup's work as pointed out by JeffE (and myself in the comment) are all for edge updates.

AFAIK, the CS theory community is only only starting to look at vertex updates for general graphs. There was a ground-breaking work on this by Chan, Pătraşcu, and Roditty in FOCS 2008. See this link for a very recent (Sept 2010) revision and the references within.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why do you think that the Holm et. al. approach does not work for my problem? I was going to adopt it. $\endgroup$ – bitmask Oct 30 '10 at 14:15
  • 1
    $\begingroup$ If your graph has bounded degree, then in theory you can emulate a vertex update using a bunch of edge updates. Otherwise, a single vertex update (say, the removal of the center of a star graph) can change the graph's connectivity drastically, and in that case you need the result of Chan et al. $\endgroup$ – Maverick Woo Oct 30 '10 at 14:51
  • $\begingroup$ I see. I should have stated in the original question, that vertex-removals are rare, so I can afford to do it edge-by-edge. $\endgroup$ – bitmask Oct 30 '10 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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