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.
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.
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:
- w := dequeue
- Remove w from its level, and put it in the next level.
- Update local neighbours:
- * For each edge w−x in local, remove it from local and put it in forward.
- * backward := local
- Update forward neighbours:
- * 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.
- * local := forward
- * forward := empty set
- If the new backward is empty, enqueue w again on Q.
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 FindRoot=FindRoot. 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 Fi a spanning forest of Gi. Our forest F from before is now called FL. We will keep a decreasing sequence of forests FL ⊇... ⊇ F0.
Operations
The Query and Insert operations use only the largest forest FL. 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 FL.When such an edge e = x−y is deleted, it is first removed from FL and from all smaller spanning forests to which it belongs, i.e. from every Fi with i ≥ level. Then we look for a replacement edge.
Start with the smallest spanning forest which contained e, namely, Fi with i = level. The edge e belongs to a certain tree T⊆Fi. After the deletion of e, the tree T is broken to two smaller trees: Tx which contains the node x and Ty which contains the node y. An edge of Gi is a replacement edge, if and only if it connects a node in Tx with a node in Ty. Suppose wlog that Tx is the smaller tree.
We loop over all the edges ε with level i and at least one node in Tx:
- If the other node of ε is in Ty, then a replacement edge is found! Add this edge to Fi and to all containing forests up to FL, and finish. The spanning forests are fixed.
- If the other node of ε is in Tx, then this is not a replacement edge, and to 'penalize' it for wasting our time, we decrease its level by 1.
Analysis
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.
The Cutset structure
Given a graph G and a subset T⊆V, define cutset 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.Start by giving a number to each vertex. Suppose there are n vertices; then each vertex can be represented by a number with lg bits. Next, give a number to each edge, which is a concatenation of the numbers of its vertices - a number with 2 lg bits.
For each vertex v, calculate and keep xor, which is the xor of the numbers of all edges adjacent to it.
Now for each subset T⊆V, it is possible to calculate xor = the xor of the values of all vertices in T. Consider an edge e = u−v which is an internal edge of T. The number of e is included twice in xor - once for u and once for v. Since the xor of every number with itself is 0, e vanishes and does not affect xor. Thus, xor is actually the xor of all edges in cutset. There are several options:
- If xor=0, then we can confidently reply that cutset is empty.
- If xor is the number of a real edge e, then probably e is the only edge in cutset, and we can return e. We can also read the endpoints of e from the number of e by splitting it to the lg leftmost bits and the lg rightmost bits.
- The third option is that xor is a nonzero number which does not represent a real edge. This can only happen if there are two or more edges in cutset, since in that case xor is the xor of several numbers of edges. In this case, we report "failure", since we know that there are edges in the cutset but cannot identify any single edge.
First, create a sequence of lg levels of the cutset structures, each of which contains about half the edges from the upper level. If in the first level xor returns an illegal value, meaning that cutset has two or more edges, then there is a chance that in the next level, which contains fewer edges, xor will return a legal value since cutset will contain a single edge. If xor still returns an illegal value, continue to the next level, etc. Since the number of edges is decreasing, there are two cases:
- The good case is that we eventually find a level in which cutset contains a single edge; then we return that edge and finish.
- The bad case is that we eventually find a level in which cutset contains no edges; then we report "failure", since we know that there are edges in the cutset but cannot identify any single edge.
Next, create a collection of C lg independent versions of the level structure, where C is a constant. In each versions, do an independent random reduction of edges from level to level. Try each query on each of the versions until one of them succeeds. The probability that all versions fail is at most:
By proper selection of C we can make the probability of failure arbitrarily close to 0.
Operations
We can add a cutset structure to a dynamic connectivity structure.The Insert and Delete operations on the cutset structure are done in exactly the same way: the edge inserted/deleted is XORed into both its endpoints.
When an edge is deleted from the spanning forest used for the dynamic connectivity structure, the cutset structure is used to find a replacement edge.
Analysis
A single cutset structure requires only O memory - only a single number, with 2 lg n bits, for each of the n vertices. We don't have to keep the edges themselves. For dense graphs, this is much cheaper than keeping the entire graph in memory.We have to keep lg versions, each of which contains lg levels. Hence, the total memory requirement is.
The query time is O in the worst case. This is in contrast to The Level structure, in which the query time is O amortized, but the worst-case time is O.
Offline Dynamic Connectivity
If the order in which edges will be deleted is known ahead of time, then we can solve the dynamic connectivity problem in log per query. If we can maintain a Maximum Spanning Forest where edges are ordered by their deletion time, we know that when we delete some edge that is in the forest, there is no possible edge that can replace it. If there were some edge that connects the same two components the deleted edge does, then this other edge would have been part of the maximum spanning forest instead of the edge we deleted. This makes the delete operation trivial: we simply need to split the tree into its two parts if the edge to delete is part of our forest, or ignore the operation otherwise.Adding an edge is slightly more complicated. If we add an edge edge e from u to v, then if u and v are not connected, then this edge will be part of the Maximum Spanning Forest. If they are connected, we want to add u->v to our forest if it can improve our Maximum Spanning Forest. To do this, we need to quickly check what edge has the smallest removal time on the path from u to v. If this edge's removal time comes after e's removal time, then e cannot improve our minimum spanning forest. Otherwise, the other edge should be deleted and replaced with e.
This requires us to do the following operations: add an edge, cut an edge, and query the minimum edge on a path which can be done rather easily with a link-cut tree in log per operation.