<p>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.</p>

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

CC BY-SA 2.5
2010-10-29T21:38:33.307Z
Jinx.  You owe me a coke.
Jeffε
CC BY-SA 2.5
2010-10-29T21:48:59.427Z
@JeffE: I did not know about [that game](http://en.wikipedia.org/wiki/Jinx_%28children%27s_game%29).  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
CC BY-SA 2.5
2010-10-29T21:58:38.057Z
if only you could trade in reputation points :)
Suresh Venkat
CC BY-SA 2.5
2010-10-29T21:36:16.550Z
2010-10-29T21:36:16.550Z
Tsuyoshi Ito
<p>(For now let me just stick with connectivity queries, which unfortunately may not be sufficient for your application.)</p>

<p>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.</p>

<p>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 <a href="http://people.csail.mit.edu/mip/papers/subconn/paper.pdf">link</a> for a very recent (Sept 2010) revision and the references within.</p>

CC BY-SA 2.5
2010-10-30T14:15:39.070Z
Why do you think that the Holm et. al. approach does not work for my problem? I was going to adopt it.
bitmask
CC BY-SA 2.5
2010-10-30T14:51:44.573Z
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.
Maverick Woo
CC BY-SA 2.5
2010-10-30T16:35:44.433Z
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.
bitmask
CC BY-SA 2.5
2010-10-30T12:56:00.937Z
2010-10-30T12:56:00.937Z
Maverick Woo
<p>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.</p>

<ul>
<li><p>Monika R. Henzinger and Valerie King.  <a href="http://portal.acm.org/citation.cfm?id=320215">Randomized fully dynamic graph algorithms with polylogarithmic time per operation</a>.  <em>Journal of the ACM</em> 46(4):502—516, 1999.</p></li>
<li><p>Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. <a href="http://portal.acm.org/citation.cfm?id=502095">Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity</a>, <em>Journal of the ACM</em> 48(4):723—760, 2001.</p></li>
<li><p>Mikkel Thorup.  <a href="http://portal.acm.org/citation.cfm?id=335345">Near-optimal fully-dynamic graph connectivity</a>.  <em>Proc. 32nd STOC</em> 343—350, 2000.</p></li>
</ul>

CC BY-SA 2.5
2010-10-29T22:20:11.037Z
This sounds awesome, once I'm through the papers, I'll most likely accept this.
bitmask
CC BY-SA 2.5
2010-10-29T21:37:56.163Z
2010-10-29T21:37:56.163Z
Jeffε
<h1>Problem</h1>

<p>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.</p>

<h2>Properties</h2>

<p>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 <em>can</em> change to $n \notin e$.</p>

<h1>Approaches</h1>

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

<h2>Slow state-less</h2>

<p>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.</p>

<h2>Stateful fast(-er) (?) approach</h2>

<p>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).</p>

<h1>Question</h1>

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

<h1>Note</h1>

<p>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.</p>

CC BY-SA 2.5
2010-10-30T02:36:51.080Z
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
CC BY-SA 2.5
2010-10-30T07:05:22.657Z
@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
CC BY-SA 2.5
2010-10-30T12:57:46.223Z
Oops, I don't know how I missed the very first sentence... See the "answer" below.
Maverick Woo
<ds.algorithms><graph-theory><approximation-algorithms><online-algorithms>
Is there an online-algorithm to keep track of components in a changing undirected graph?
bitmask
# Is there an online-algorithm to keep track of components in a changing undirected graph?

(Asked by: username_0 on 2010-10-29)

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

**Tags:** ds.algorithms, graph-theory, approximation-algorithms, online-algorithms

> **Comments:**
> **username_1**: 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.)  
> **username_0**: @username_1: 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?  
> **username_1**: Oops, I don't know how I missed the very first sentence... See the "answer" below.  

---

## 3 answers

### Answer by username_3 on 2010-10-29. Score: 19 | Accepted answer

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.

* Monika R. Henzinger and Valerie King. [Randomized fully dynamic graph algorithms with polylogarithmic time per operation](http://portal.acm.org/citation.cfm?id=320215). *Journal of the ACM* 46(4):502—516, 1999.
* Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. [Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity](http://portal.acm.org/citation.cfm?id=502095), *Journal of the ACM* 48(4):723—760, 2001.
* Mikkel Thorup. [Near-optimal fully-dynamic graph connectivity](http://portal.acm.org/citation.cfm?id=335345). *Proc. 32nd STOC* 343—350, 2000.

> **Comments:**
> **username_0**: This sounds awesome, once I'm through the papers, I'll most likely accept this.  

---

### Answer by username_2 on 2010-10-29. Score: 8

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>

> **Comments:**
> **username_3**: Jinx.  You owe me a coke.  
> **username_2**: @JeffE: I did not know about [that game](http://en.wikipedia.org/wiki/Jinx_%28children%27s_game%29).  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.  
> **username_4**: if only you could trade in reputation points :)  

---

### Answer by username_1 on 2010-10-30. Score: 5

(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](http://people.csail.mit.edu/mip/papers/subconn/paper.pdf) for a very recent (Sept 2010) revision and the references within.

> **Comments:**
> **username_0**: Why do you think that the Holm et. al. approach does not work for my problem? I was going to adopt it.  
> **username_1**: 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.  
> **username_0**: 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.  

---

