4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jukka Suomela Jun 29 '18 at 8:41
  • 1
    $\begingroup$ @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... $\endgroup$ – Neal Young Jun 30 '18 at 4:19
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

Dynamic Graph Algorithms with Applications

Dynamic Graph Algorithms for Connectivity Problems

$\endgroup$
  • 1
    $\begingroup$ If it is not an answer to the question why not making it a comment? $\endgroup$ – Saeed Jun 28 '18 at 14:50
  • $\begingroup$ @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. $\endgroup$ – Shaull Jun 28 '18 at 15:38
  • $\begingroup$ Fair enough, however you can rephrase your answer (remove the first sentence) and elaborate a bit more, e.g. explain what those papers achieve. $\endgroup$ – Saeed Jun 28 '18 at 22:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Kai Jun 29 '18 at 8:44
  • $\begingroup$ @Saeed The last link here seems to have the answer. $\endgroup$ – Kai Jun 29 '18 at 8:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.