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 (this can be called incremental connectivity); Edges are only deleted from the graph (this can be called decremental connectivity); Edges can be either added or deleted (this can be called fully dynamic connectivity).
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?" (equivalently: "do vertices x and y belong to the same connected component?").
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 (using any tree scan algorithm, such as DFS). 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 (make a step of first scan, then a step of the second scan, then a step of the first scan, etc.). Suppose the first scan that terminates is the scan from u (so we know that the tree containing u is the smaller one). 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 (connected by other edges) or broken to two components. So we use two processes which run in parallel (or in an interleaved way). 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 (BFS), 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 (there is at least one such edge, which may be artificial), local edges which connect it to other edges in level i (there are zero or more such edges), or forward edges which connect it to edges in level i+1 (there are zero or more such edges). So for each vertex v, we maintain three sets of edges (backward, local and forward).
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 (and therefore process A is halted too). 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(u) and from backward(v). Case 2.1 If the new backward(v) is not empty, then the components have not changed: there are other edges which connect v backwards. Process B halts (and process A is halted too). Case 2.2 If the new backward(v) is empty, then v is no longer connected to level i−1, and so its distance from the root is no longer i; it must be at least i+1. Additionally, there may be other vertices, connected to v, whose distance from the root increases as a result of the deletion. To calculate the updated distances, we use a queue Q, which initially contains only the vertex v.
While Q is not empty: w := dequeue(Q) Remove w from its level (say, j), and put it in the next level (j+1). Update local neighbours: For each edge w−x in local(w), remove it from local(x) and put it in forward(x). backward(w) := local(w) Update forward neighbours: For each edge w-x in forward(w), remove it from backward(x) and put it in local(x); if the new backward(x) is empty, enqueue x on Q. local(w) := forward(w) forward(w) := empty set If the new backward(w) 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 .One way to realize the return to the structure preceding the deletion of e without having to copy the whole structure is to keep on a stack all the changes that took place in the BFS structure since the deletion of e and undo them one by one. This way the processing time is only multiplied by a constant.
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(log(n)).
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.Dynamic Graph Problems - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.
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(e). Then we look for a replacement edge.
Start with the smallest spanning forest which contained e, namely, F with i = level(e). 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 (i.e. contains at most half the nodes of T; we can tell the size of each subtree by an annotation added to the Euler trees).
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 (using the ET tree operations). 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 (again using the ET operations).
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.
The Cutset structure Given a graph G(V, E) and a subset T⊆V, define cutset(T) as the set of edges that connect T with V\T. The cutset structure is a data structure that, without keeping the entire graph in memory, can quickly find an edge in the cutset, if such an edge exists.