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 (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 ${\displaystyle \Theta (\alpha (n))}$, where n is the number of vertices and α is the inverse Ackermann function. ^{[1] [2]}

Decremental connectivity

The case in which edges can only be deleted was solved by Shimon Even and Yossi Shiloach. ^[3]

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 ${\displaystyle O(\log(n))}$.

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 ${\displaystyle O(\log(n))}$.

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:

1. w := dequeue(Q)
2. Remove w from its level (say, j), and put it in the next level (j+1).
3. 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)
4. 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
5. 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 v with any vertices which are not v's descendants, except the artificial edge ⁠${\displaystyle u-v}$⁠. ^[4]

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 ${\displaystyle |V|-1}$, the cost per edge is bounded by ${\displaystyle 2|V|}$. Hence the amortized time per deletion operation is ${\displaystyle O(n)}$.

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 ${\displaystyle \mathrm {FindRoot} (x)=\mathrm {FindRoot} (y)}$. 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 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. ^{[5] [6]}

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(e). Then we look for a replacement edge.

Start with the smallest spanning forest which contained e, namely, Fi with i = level(e). 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 (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 Tx by 1. Then 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. 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 Tx, 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 2ⁱ. Hence the level of an edge is always at least 0.

Each edge whose level is decreased, takes ${\displaystyle O(\lg n)}$ time to find (using the ET tree operations). In total, each inserted edge takes ${\displaystyle O(\lg ^{2}n)}$ time until it is deleted, so the amortized time for deletion is ${\displaystyle O(\lg ^{2}n)}$. The remaining part of delete also takes ${\displaystyle O(\lg ^{2}n)}$ time, since we have to delete the edge from at most ${\displaystyle O(\lg n)}$ levels, and deleting from each level takes ${\displaystyle O(\lg n)}$ (again using the ET operations).

In total, the amortized time per update is ${\displaystyle O(\lg ^{2}n)}$. The time per query can be improved to ${\displaystyle O(\lg n/\lg \lg n)}$.

However, the worst-case time per update might be ${\displaystyle O(n)}$. 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. ^[7]

Start by giving a number to each vertex. Suppose there are n vertices; then each vertex can be represented by a number with lg(n) bits. Next, give a number to each edge, which is a concatenation of the numbers of its vertices - a number with 2 lg(n) bits.

For each vertex v, calculate and keep xor(v), 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(T) = the xor of the values of all vertices in T. Consider an edge e = u−v which is an internal edge of T (i.e. both u and v are in T). The number of e is included twice in xor(T) - once for u and once for v. Since the xor of every number with itself is 0, e vanishes and does not affect xor(T). Thus, xor(T) is actually the xor of all edges in cutset(T). There are several options:

• If xor(T)=0, then we can confidently reply that cutset(T) is empty.
• If xor(T) is the number of a real edge e, then probably e is the only edge in cutset(T), and we can return e. We can also read the endpoints of e from the number of e by splitting it to the lg(n) leftmost bits and the lg(n) rightmost bits.
• The third option is that xor(T) is a nonzero number which does not represent a real edge. This can only happen if there are two or more edges in cutset(T), since in that case xor(T) 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. ^[8]

Our goal now is to handle this third option.

First, create a sequence of lg(n) levels of the cutset structures, each of which contains about half the edges from the upper level (i.e., for each level, pick each edge from the upper level with probability 1/2). If in the first level xor(T) returns an illegal value, meaning that cutset(T) has two or more edges, then there is a chance that in the next level, which contains fewer edges, xor(T) will return a legal value since cutset(T) will contain a single edge. If xor(T) 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(T) contains a single edge; then we return that edge and finish.
• The bad case is that we eventually find a level in which cutset(T) contains no edges; then we report "failure", since we know that there are edges in the cutset but cannot identify any single edge.

It is possible to prove that the probability of success is at least 1/9.

Next, create a collection of C lg(n) 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:

${\displaystyle (1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}}$

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(n lg n) 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(n) versions, each of which contains lg(n) levels. Hence, the total memory requirement is ⁠${\displaystyle O(n\lg ^{3}n)}$⁠.

The query time is O(polylog(n)) in the worst case. This is in contrast to the Level structure, in which the query time is O(polylog(n)) amortized, but the worst-case time is O(n).

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 time ${\displaystyle O(\log n)}$ 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 maximum 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(n) per operation.

See also

• Dynamic problem (algorithms)
• Partition refinement

References

1. Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM. 22 (2): 215–225. CiteSeerX   10.1.1.399.6704 . doi:10.1145/321879.321884. S2CID   11105749.
2. Tarjan, Robert Endre (1979). "A class of algorithms which require non-linear time to maintain disjoint sets". Journal of Computer and System Sciences. 18 (2): 110–127. doi: 10.1016/0022-0000(79)90042-4 .
3. Shiloach, Y.; Even, S. (1981). "An On-Line Edge-Deletion Problem". Journal of the ACM. 28: 1–4. doi:10.1145/322234.322235. S2CID   207746822.
4. 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.
5. Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity". Journal of the ACM. 48 (4): 723. doi:10.1145/502090.502095. S2CID   7273552.
6. Dynamic Graph Problems - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.
7. Kapron, B. M.; King, V.; Mountjoy, B. (2013). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. doi:10.1137/1.9781611973105.81. ISBN   978-1-61197-251-1.
8. There is a small probability that the xor of several different edges will result in a number which happens to be the number of another edge. This might lead to a false positive. In order to reduce the probability of this event, we can enlarge the domain of the numbers of vertices to, say, n³ instead of n. Then, if there is more than one edge in cutset(T), xor(T) will almost certainly be a meaningless value, as stated above.

• See also: Thorup, M. (2000). Near-optimal fully-dynamic graph connectivity. Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00. p. 343. doi:10.1145/335305.335345. ISBN   1581131844.