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

-
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.) –  Maverick Woo Oct 30 '10 at 2:36
@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? –  bitmask Oct 30 '10 at 7:05
Oops, I don't know how I missed the very first sentence... See the "answer" below. –  Maverick Woo Oct 30 '10 at 12:57

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.

-
This sounds awesome, once I'm through the papers, I'll most likely accept this. –  bitmask Oct 29 '10 at 22:20

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

-
Jinx. You owe me a coke. –  JɛﬀE Oct 29 '10 at 21:38
@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. –  Tsuyoshi Ito Oct 29 '10 at 21:48
if only you could trade in reputation points :) –  Suresh Venkat Oct 29 '10 at 21:58