8
$\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$
2
  • 2
    $\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$ Jun 29, 2018 at 8:41
  • 4
    $\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, 2018 at 4:19

3 Answers 3

6
$\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$
5
$\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$
7
  • 2
    $\begingroup$ If it is not an answer to the question why not making it a comment? $\endgroup$
    – Saeed
    Jun 28, 2018 at 14:50
  • 1
    $\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, 2018 at 15:38
  • 1
    $\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, 2018 at 22:10
  • 2
    $\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, 2018 at 8:44
  • 1
    $\begingroup$ @Saeed The last link here seems to have the answer. $\endgroup$
    – Kai
    Jun 29, 2018 at 8:45
4
$\begingroup$

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.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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