Dynamic connectivity
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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?").
Evidence and sources
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?"). 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.
How it works
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 |V|-1 , the cost per edge is bounded by 2|V| .
Hence the amortized time per deletion operation is O(n) . 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 \mathrm{FindRoot}(x)=\mathrm{FindRoot}(y) . The amortized update time and query time are both O(log(n)). 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 . 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.
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. 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: (1-1/9)^{C \lg{n}} = 2^{- 0.17C \lg{n}} = n^{-0.17 C} By proper selection of C we can make the probability of failure arbitrarily close to 0.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368654410 under CC BY-SA 4.0; modifications have been made.