# 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? – Jukka Suomela Jun 29 '18 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... – Neal Young Jun 30 '18 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.