Dynamic connectivity


In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.
The set V of vertices of the graph is fixed, but the set E of edges can change. The three cases, in order of difficulty, are:
  • Edges are only added to the graph ;
  • Edges are only deleted from the graph ;
  • Edges can be either added or deleted.
After each addition/deletion of an edge, the dynamic connectivity structure should adapt itself such that it can give quick answers to queries of the form "is there a path between x and y?".

Incremental connectivity

If edges can only be added, then the dynamic connectivity problem can be solved by a disjoint-set data structure. Each set represents a connected component; there is a path between x and y if and only if they belong to the same set. The amortized time per operation is, where n is the number of vertices and α is the inverse Ackermann function.

Decremental connectivity

The case in which edges can only be deleted was solved by Shimon Even and Yossi Shiloach.
The structure uses a table that specifies, for each vertex, the name of the component to which it belongs. Thus a connectivity query takes constant time. The challenge is to update the table when an edge is deleted.

Acyclic graphs (forests)

When edge u-''v is deleted in a forest, the tree containing that edge is broken to two trees: one of them contains u'' and the other contains v. The table is updated in the following way.
  • Scan the tree starting from u.
  • Scan the tree starting from v.
  • Do the above two procedures in parallel, i.e., either using two parallel processes, or by interleaving their steps.
  • Suppose the first scan that terminates is the scan from u. Assign a new component name to every node in the subtree of u.
Since we always rename the smaller sub-component, the amortized time for a delete operation is.

General graphs

When an edge is deleted in a general graph, we don't know whether its component remains a single component or broken to two components. So we use two processes which run in parallel. Process A checks whether the edge deletion breaks a component, and if it does, both processes halt. Process B checks whether the edge deletion does not break the component to which it belongs, and if it does not, again both processes halt.
;Process A: is similar to the acyclic-graph case: there are two sub-processes who scan from both ends of the deleted edge. If one of the sub-processes finishes before reaching the other end, this means that the component is broken into two sub-components, and the name of the smaller sub-component is updated, as before. Thus the amortized time for a delete operation is again.
;Process B: uses a breadth-first structure, which is initialized as follows. A vertex r is chosen and the BFS starts from it. The only vertex in level 0 is r. All the vertices of distance i from the root are in level i. If G is not connected, a new scan is started at some unscanned vertex v, v is put in level 1, and an artificial edge connects v to the root r; all vertices of distance i from v are now in level i+1, etc. Artificial edges are introduced in order to keep all the connected components in one BFS structure and are used only for this purpose. Clearly, the artificial edges are used only in process B.
The structure has the following properties. A vertex v in level i, i>0, has only three types of edges: backward edges which connect it to level i−1, local edges which connect it to other edges in level i, or forward edges which connect it to edges in level i+1. So for each vertex v, we maintain three sets of edges.
When an edge u-''v is deleted, there are two options: either u'' and v are in the same level, or they are in levels whose number differs by 1.
;Case 1: both u and v are on the same level. In this case, the edge deletion cannot change the components. The edge is simply deleted from the sets of local edges of u and v, and process B halts. Our BFS structure is still valid.
;Case 2: u and v are on different levels. Without loss of generality, assume u is in level i−1 and v is in level i; hence the edge should be removed from forward and from backward.
While Q is not empty:
  1. w := dequeue
  2. Remove w from its level, and put it in the next level.
  3. Update local neighbours:
  4. * For each edge w−x in local, remove it from local and put it in forward.
  5. * backward := local
  6. Update forward neighbours:
  7. * For each edge w-''x in forward, remove it from backward and put it in local; if the new backward is empty, enqueue x'' on Q.
  8. * local := forward
  9. * forward := empty set
  10. If the new backward is empty, enqueue w again on Q.
If the edge deletion does not break any component and we are in case 2.2, then eventually the procedure will halt. In this case it is easy to see that the BFS structure is maintained correctly. If its deletion does break a component, then the procedure will not halt by itself. However, process A, recognizing the break, will halt, and both processes will halt. In this case all the changes made in the BFS structure are ignored, and we go back to the BFS structure we had just before the deletion, except that the deleted edge is now replaced by an artificial edge. Clearly, in this case v is now the root of a tree which includes the new component, and perhaps additional components, through some other artificial edges. Also, there are no edges connecting the descendants of
with any vertices which are not 's descendants, except the artificial edge.
whenever an edge is processed in the procedure, one of its endpoints drops by one level. Since the lowest level a vertex can reach in runs which are terminated by process B is, the cost per edge is bounded by. Hence the amortized time per deletion operation is.

Fully dynamic connectivity

Acyclic graphs (forests)

A forest can be represented using a collection of either link-cut trees or Euler tour trees. Then the dynamic connectivity problem can be solved easily, as for every two nodes x,y, x is connected to y if and only if. The amortized update time and query time are both O.

General graphs

A general graph can be represented by its spanning forest - a forest which contains a tree for every connected component of the graph. We call this spanning forest F. F itself can be represented by a forest of Euler tour trees.
The Query and Insert operations are implemented using the corresponding operations on the ET trees representing F. The challenging operation is Delete, and in particular, deleting an edge which is contained in one of the spanning trees of F. This breaks the spanning tree into two trees, but, it is possible that there is another edge which connects them. The challenge is to quickly find such a replacement edge, if it exists. This requires a more complex data structure. Several such structures are described below.

The Level structure

Each edge in the graph is assigned a level. Let L = lg n. The level of each edge inserted to the graph is initialized to L, and may decrease towards 0 during delete operations.
For each i between 0 and L, define Gi as the subgraph consisting of edges that are at level i or less, and F a spanning forest of Gi. Our forest F from before is now called F. We will keep a decreasing sequence of forests F ⊇... ⊇ F.
Operations
The Query and Insert operations use only the largest forest F. The smaller subgraphs are consulted only during a Delete operation, and in particular, deleting an edge which is contained in one of the spanning trees of F.
When such an edge e = x−y is deleted, it is first removed from F and from all smaller spanning forests to which it belongs, i.e. from every F with i ≥ level. Then we look for a replacement edge.
Start with the smallest spanning forest which contained e, namely, F with i = level. The edge e belongs to a certain tree T⊆''F. After the deletion of e'', the tree T is broken to two smaller trees: T which contains the node x and T which contains the node y. An edge of Gi is a replacement edge, if and only if it connects a node in T with a node in T. Suppose wlog that T is the smaller tree.
We first decrease the level of each edge of T by 1. Then we loop over all the edges ε with level i and at least one node in T:
  • If the other node of ε is in T, then a replacement edge is found! Add this edge to F and to all containing forests up to F, and finish. The spanning forests are fixed. Notice that in order to pay for this search, we decrease the level of the edges visited during the search.
  • If the other node of ε is in T, then this is not a replacement edge, and to 'penalize' it for wasting our time, we decrease its level by 1.
    Analysis
The level of each edge will be decreased at most lg n times. Why? Because with each decrease, it falls into a tree whose size is at most half the size of its tree in the previous level. So in each level i, the number of nodes in each connected component is at most 2i. Hence the level of an edge is always at least 0.
Each edge whose level is decreased, takes time to find. In total, each inserted edge takes time until it is deleted, so the amortized time for deletion is . The remaining part of delete also takes time, since we have to delete the edge from at most levels, and deleting from each level takes .
In total, the amortized time per update is. The time per query can be improved to.
However, the worst-case time per update might be. The question of whether the worst-case time can be improved had been an open question, until it was solved in the affirmative by the Cutset structure.