Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

Question

I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if my terminology is not exactly right.

I have a database system where user can add/remove/move objects by creating/deleting and altering relationships. As such, I can see the objects as been vertices in a graph and the relationships been edges and edges can be weighted depending on the type of relationships (either composition, association, or aggregation).

From the user's point of view, adding a new element can be a single click and underneath the hood, the program creates a graph of objects linked by relationships. This graph, is then added to the main graph that defines the entire database. Removing an element, would be the reverse where links/edges are disconnected and the graph becomes two disjoint graphs where 1 is the database, and the other consists of vertices formed by the element and its sub elements.

I need a really quick way to determine when I have a disjoint graphs and when 2 disjoint graphs becomes 1 again. I had a brief look at Holm, de Lichtenberg, and Thorup (2001; pdf). It seems like the way to go, but the author did mention they are only considering a graph with fixed number of vertices. Just wondering do algorithms usually extend themselves to adding/removal of vertices by just performing the adding of edges incrementally? Or has there been works that tailors specifically for such scenario?

Answer 1

This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for.

You could also try Bhadra & Ferreira, they're probably getting a bit off-topic for what you want, but they do have references to other material that could be useful.

Answer 2

The Vertex updates can be handled using edge updates as follows (Although a bit inefficient as it makes deg(u) calls to edge update function):

AddVertex(G,u,Adj(u)):- 
  /* Adj(u) is the vertices adjacent to u after adding u */  
  For each v in Adj(u) do 
    AddEdge(G, (u,v))

DeleteVertex(G,u):- 
  For each v in Adj(u) do
    DeleteEdge(G, (u,v)) 

Thorup et. Al's running time analysis states that their update time is amortised time per edge update. So, It doesn't directly imply any poly. logarithmic update time result under vertex updates.

There are some works where the update operation supports vertex/addition deletion as well. In [1] for Dynamic All Pairs Shortest Paths problem, they basically allow updating edges incident on a vertex by specifying the new weights. We can update them all to +infinity for deleting a vertex and similarly for adding a vertex.

You might find the references [2], and [3] helpful if you are just starting with dynamic graph algorithms. [2] gives a good high level idea of current approaches to dynamic connectivity problem.

References

1. A new approach to dynamic All pairs shortest paths, Demetrescu. et. Al, JACM 2004 Voume 51 issue 6, 2004

2. Slide of Talk on Dynamic graph Algorithms by Dr. Surender Baswana in "Recent advances in data structures and algorithms" workshop held at IMSc, Chennai.

3. Camil Demetrescu and Pino Italiano, Dynamic graphs, Handbook on Data Structures and Applications, Chapter 36. Dinesh Mehta and Sartaj Sahni (eds.), CRC Press Series, in Computer and Information Science, January 2005. [Draft (pdf)]

Answer 3

Holm et. al's algorithm works with an arbitrary number of vertices, though it isn't so clear from the description. The main difficulty in their presentation is how they label the levels of the forest. If instead of setting the largest level forest to $F_{lg(n)}$, you start counting from $F_0$ up and modify invariant 2 such that every tree in level i has size at most $\frac{n}{2^i}$ instead of $2^i$, then there is no longer a bound on the number of vertices in the graph and you can freely insert and delete them as you choose.

For an example implementation of this (in JavaScript) you can take a look a the following GitHub repository:

https://github.com/mikolalysenko/dynamic-forest