<p>This question falls under "dynamic graph algorithms", which has been extensively studied in recent years. </p>

<p>Dynamic graph algorithms consider a given graph, which is then modified using certain allowed operations, e.g. edge removal, insertion, etc. The aim is to develop data structures to support queries about various properties of the graph.</p>

<p>Some literature you can start with:</p>

<p><a href="https://dl.acm.org/citation.cfm?id=1882766" rel="nofollow noreferrer">Dynamic Graph Algorithms</a></p>

<p><a href="https://link.springer.com/chapter/10.1007/3-540-44985-X_1" rel="nofollow noreferrer">Dynamic Graph Algorithms with Applications</a></p>

<p><a href="https://pdfs.semanticscholar.org/cb80/5b808babef4697117f83859a6d50fdee5799.pdf" rel="nofollow noreferrer">Dynamic Graph Algorithms
for Connectivity Problems</a></p>

CC BY-SA 4.0
2018-06-28T14:50:46.550Z
If it is not an answer to the question why not making it a comment?
Saeed
CC BY-SA 4.0
2018-06-28T15:38:19.780Z
@Saeed - to get some of them sweet sweet upvotes :)
I'm fine if a moderator wants to turn it into a comment. I think it does have merit as an answer, as it points in the right research direction. That is, had the OP asked if this topic has been studied under some name, then this would be a valid answer.
Shaull
CC BY-SA 4.0
2018-06-28T22:10:10.783Z
Fair enough, however you can rephrase your answer (remove the first sentence) and elaborate a bit more, e.g. explain what those papers achieve.
Saeed
CC BY-SA 4.0
2018-06-29T08:44:44.140Z
You should look more carefully before you say it's not an answer :P The last link has the answer (although not as good an answer, in theory, as the one linked by @hemant). I'll accept an answer once I have a working implementation.
Kai
CC BY-SA 4.0
2018-06-29T08:45:42.053Z
@Saeed The last link here seems to have the answer.
Kai
CC BY-SA 4.0
2018-06-29T08:56:30.290Z
Also, I was not aware of the key term "dynamic graph algorithms". Pointing this out was genuinely helpful. Had I known this, I would have been able to google up a solution.
Kai
CC BY-SA 4.0
2018-07-06T04:06:43.697Z
@Kai, first understand what I wrote then suggest me anything.
Saeed
CC BY-SA 4.0
2018-06-28T11:46:48.670Z
2018-06-29T07:57:04.697Z
2018-06-29T07:57:04.697Z
Shaull
<p>I see this question only 2.5 years after, but I think I have a relevant answer.  Indeed, it is at the core of the work we have done on <a href="https://arxiv.org/abs/cs/0502085" rel="nofollow noreferrer">Fast generation of random <em>connected</em> graphs with prescribed degrees</a>.</p>
<p>In this paper, we start with a connected graph, and perform large numbers of edge swaps in order to make it random. We however want to obtain a random <em>connected</em> graph, so we must ensure that these (series of) swaps do not disconnect the graph. We therefore perform many connectivity tests, and these turn out to be the costly part of the method. The trick is that <strong>we do not have to test after each edge swap</strong>; instead, we estimate how often a test is likely to be needed.</p>
<p>Of course, this leads to two problems:</p>
<ul>
<li>when we make a connectivity test, the graph may have been disconnected for a long time (since last connectivity test); we then have to cancel the swaps, and this is why choosing appropriate frequency for connectivity tests is crucial;</li>
<li>a sequence of edge swaps may disconnect the graph and then reconnect it, without us knowing (since we do not test connectivity at each swap); this has no importance for the random generation, though.</li>
</ul>
<p>This is an angle quite different from other answers, but it is strongly related to the question, imho. While others focus on the &quot;edge swap&quot; part of the question, <strong>this answer is more concerned with the &quot;repeated&quot; part</strong> of &quot;repeated edge swaps&quot;.</p>

CC BY-SA 4.0
2021-01-05T10:35:51.430Z
2021-02-15T09:15:11.493Z
2021-02-15T09:15:11.493Z
Matthieu Latapy
<p>Check this paper <a href="https://arxiv.org/pdf/1209.5608.pdf" rel="noreferrer">https://arxiv.org/pdf/1209.5608.pdf</a> which uses cluster forest which support operations like:</p>

<p>connected(u, v) : if vertex u and v are connected , 
insert(u, v) : Insert edge (u, v) 
delete(u, v) : delete edge (u, v) </p>

<p>It answers your query in O(log n / log log n) time with O(log2n / log log n) update time.</p>

CC BY-SA 4.0
2018-06-28T18:30:22.090Z
2018-06-28T18:30:22.090Z
user2749282
<p>Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after <em>repeated</em> modifications, specifically: repeated edge swaps. An edge swap removes two edges $\{a - b, c-d\}$ and adds $\{a-c, b-d\}$ instead.  Is there a way to do better than a full linear-time check after each and every modification?</p>

CC BY-SA 4.0
2018-06-29T08:41:24.590Z
Can anyone see a simple argument that would show that checking connectivity in this case is as hard as checking connectivity in general dynamic graphs?
Jukka Suomela
CC BY-SA 4.0
2018-06-30T04:19:28.307Z
@JukkaSuomela, yes.  Starting with a complete graph $G=(V,V\times V)$, replace each edge $(u,w)$ by a gadget consisting of four new vertices $\{A, B, C, D\}$ and edges $(u, A), (A, B), (u, B)$ and $(w,C), (w, D), (C, D)$.  Then swapping $\{(A,B), (C,D)\}$ for $\{(A,C), (B,D)\}$ (or vice versa) is like adding (or removing) the edge $(u, w)$.  So you can simulate a dynamic graph with arbitrary edge insertions and deletions using just edge swaps...
Neal Young
<graph-theory><graph-algorithms>
Check if graph stays connected after edge swap
Kai
# Check if graph stays connected after edge swap

(Asked by: username_0 on 2018-06-28)

Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after *repeated* modifications, specifically: repeated edge swaps. An edge swap removes two edges $\{a - b, c-d\}$ and adds $\{a-c, b-d\}$ instead. Is there a way to do better than a full linear-time check after each and every modification?

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Can anyone see a simple argument that would show that checking connectivity in this case is as hard as checking connectivity in general dynamic graphs?  
> **username_2**: @JukkaSuomela, yes.  Starting with a complete graph $G=(V,V\times V)$, replace each edge $(u,w)$ by a gadget consisting of four new vertices $\{A, B, C, D\}$ and edges $(u, A), (A, B), (u, B)$ and $(w,C), (w, D), (C, D)$.  Then swapping $\{(A,B), (C,D)\}$ for $\{(A,C), (B,D)\}$ (or vice versa) is like adding (or removing) the edge $(u, w)$.  So you can simulate a dynamic graph with arbitrary edge insertions and deletions using just edge swaps...  

---

## 3 answers

### Answer by username_6 on 2018-06-28. Score: 6 | Accepted answer

Check this paper <https://arxiv.org/pdf/1209.5608.pdf> which uses cluster forest which support operations like:

connected(u, v) : if vertex u and v are connected ,
insert(u, v) : Insert edge (u, v)
delete(u, v) : delete edge (u, v)

It answers your query in O(log n / log log n) time with O(log2n / log log n) update time.


---

### Answer by username_3 on 2018-06-28. Score: 5

This question falls under "dynamic graph algorithms", which has been extensively studied in recent years.

Dynamic graph algorithms consider a given graph, which is then modified using certain allowed operations, e.g. edge removal, insertion, etc. The aim is to develop data structures to support queries about various properties of the graph.

Some literature you can start with:

[Dynamic Graph Algorithms](https://dl.acm.org/citation.cfm?id=1882766)

[Dynamic Graph Algorithms with Applications](https://link.springer.com/chapter/10.1007/3-540-44985-X_1)

[Dynamic Graph Algorithms
for Connectivity Problems](https://pdfs.semanticscholar.org/cb80/5b808babef4697117f83859a6d50fdee5799.pdf)

> **Comments:**
> **username_4**: If it is not an answer to the question why not making it a comment?  
> **username_3**: @username_4 - to get some of them sweet sweet upvotes :) I'm fine if a moderator wants to turn it into a comment. I think it does have merit as an answer, as it points in the right research direction. That is, had the OP asked if this topic has been studied under some name, then this would be a valid answer.  
> **username_4**: Fair enough, however you can rephrase your answer (remove the first sentence) and elaborate a bit more, e.g. explain what those papers achieve.  
> **username_0**: You should look more carefully before you say it's not an answer :P The last link has the answer (although not as good an answer, in theory, as the one linked by @hemant). I'll accept an answer once I have a working implementation.  
> **username_0**: @username_4 The last link here seems to have the answer.  
> **username_0**: Also, I was not aware of the key term "dynamic graph algorithms". Pointing this out was genuinely helpful. Had I known this, I would have been able to google up a solution.  
> **username_4**: @username_0, first understand what I wrote then suggest me anything.  

---

### Answer by username_5 on 2021-01-05. Score: 4

I see this question only 2.5 years after, but I think I have a relevant answer. Indeed, it is at the core of the work we have done on [Fast generation of random *connected* graphs with prescribed degrees](https://arxiv.org/abs/cs/0502085).

In this paper, we start with a connected graph, and perform large numbers of edge swaps in order to make it random. We however want to obtain a random *connected* graph, so we must ensure that these (series of) swaps do not disconnect the graph. We therefore perform many connectivity tests, and these turn out to be the costly part of the method. The trick is that **we do not have to test after each edge swap**; instead, we estimate how often a test is likely to be needed.

Of course, this leads to two problems:

* when we make a connectivity test, the graph may have been disconnected for a long time (since last connectivity test); we then have to cancel the swaps, and this is why choosing appropriate frequency for connectivity tests is crucial;
* a sequence of edge swaps may disconnect the graph and then reconnect it, without us knowing (since we do not test connectivity at each swap); this has no importance for the random generation, though.

This is an angle quite different from other answers, but it is strongly related to the question, imho. While others focus on the "edge swap" part of the question, **this answer is more concerned with the "repeated" part** of "repeated edge swaps".


---

