# Check if graph stays connected after edge swap

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?

• 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? Jun 29, 2018 at 8:41
• @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... Jun 30, 2018 at 4:19

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.

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.

Dynamic Graph Algorithms

Dynamic Graph Algorithms with Applications

Dynamic Graph Algorithms for Connectivity Problems

• If it is not an answer to the question why not making it a comment? Jun 28, 2018 at 14:50
• @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. Jun 28, 2018 at 15:38
• Fair enough, however you can rephrase your answer (remove the first sentence) and elaborate a bit more, e.g. explain what those papers achieve. Jun 28, 2018 at 22:10
• 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
Jun 29, 2018 at 8:44