Dynamic Graphs:Connectivity

Connectivity

In this section and in Section 36.5 we consider dynamic problems on undirected graphs, showing how to deploy some of the techniques and data structures presented in Section 36.2 to obtain efficient algorithms. These algorithms maintain efficiently some property of an undirected graph that is undergoing structural changes defined by insertion and deletion of edges, and/or updates of edge costs. To check the graph property throughout a sequence of these updates, the algorithms must be prepared to answer queries on the graph property efficiently. In particular, in this section we address the fully dynamic connectivity problem, where we are interested in algorithms that are capable of inserting edges, deleting edges, and answering a query on whether the graph is connected, or whether two vertices are in the same connected component. We recall that the goal of a dynamic algorithm is to minimize the amount of recomputation required after each update. All the dynamic algorithms that we describe are able to maintain dynamically the graph property at a cost (per update operation) which is significantly smaller than the cost of recomputing the graph property from scratch.

Updates in O(log2 n) Time

In this section we give a high level description of the fastest deterministic algorithm for the fully dynamic connectivity problem in undirected graphs [22]: the algorithm, due to Holm, de Lichtenberg and Thorup, answers connectivity queries in O(log n/ log log n) worst-case running time while supporting edge insertions and deletions in O(log2n) amortized time.

Similarly to the randomized algorithm in [20], the deterministic algorithm in [22] maintains a spanning forest F of the dynamically changing graph G. As above, we will refer to the edges in F as tree edges. Let e be a tree edge of forest F , and let T be the tree of F containing it. When e is deleted, the two trees T1 and T2 obtained from T after the deletion of e can be reconnected if and only if there is a non-tree edge in G with one endpoint in T1 and the other endpoint in T2. We call such an edge a replacement edge for e. In other words, if there is a replacement edge for e, T is reconnected via this replacement edge; otherwise, the deletion of e creates a new connected component in G.

To accommodate systematic search for replacement edges, the algorithm associates to each edge e a level R(e) and, based on edge levels, maintains a set of sub-forests of the spanning forest F : for each level i, forest Fi is the sub-forest induced by tree edges of level

≥ i. If we denote by L denotes the maximum edge level, we have that:

F = F0 ⊇ F1 ⊇ F2 ⊇ ... ⊇ FL,

Initially, all edges have level 0; levels are then progressively increased, but never decreased. The changes of edge levels are accomplished so as to maintain the following invariants, which obviously hold at the beginning.

Invariant (1): F is a maximum spanning forest of G if edge levels are interpreted as weights.

Invariant (2): The number of nodes in each tree of Fi is at most n/2i.

Invariant (1) should be interpreted as follows. Let (u, v) be a non-tree edge of level R(u, v) and let u ··· v be the unique path between u and v in F (such a path exists since F is a spanning forest of G). Let e be any edge in u ··· v and let R(e) be its level. Due to (1), R(e) ≥ R(u, v). Since this holds for each edge in the path, and by construction FR(u,v) contains all the tree edges of level ≥ R(u, v), the entire path is contained in FR(u,v), i.e., u and v are connected in FR(u,v) .

Invariant (2) implies that the maximum number of levels is L ≤ llog2 nJ.

Note that when a new edge is inserted, it is given level 0. Its level can be then increased at most llog2 nJ times as a consequence of edge deletions. When a tree edge e = (v, w) of level R(e) is deleted, the algorithm looks for a replacement edge at the highest possible level, if any. Due to invariant (1), such a replacement edge has level R ≤ R(e). Hence, a replacement subroutine Replace((u, w),R(e)) is called with parameters e and R(e). We now sketch the operations performed by this subroutine.

Replace((u, w),R) finds a replacement edge of the highest level ≤ R, if any. If such a replacement does not exist in level R, we have two cases: if R > 0, we recurse on level R − 1; otherwise, R = 0, and we can conclude that the deletion of (v, w) disconnects v and w in G.

During the search at level R, suitably chosen tree and non-tree edges may be promoted at higher levels as follows. Let Tv and Tw be the trees of forest FR obtained after deleting (v, w) and let, w.l.o.g., Tv be smaller than Tw. Then Tv contains at most n/2R+1 vertices, since Tv ∪ Tw ∪ {(v, w)} was a tree at level R and due to invariant (2). Thus, edges in Tv of level R can be promoted at level R + 1 by maintaining the invariants. Non-tree edges incident to Tv are finally visited one by one: if an edge does connect Tv and Tw, a replacement edge has been found and the search stops, otherwise its level is increased by 1.

We maintain an ET-tree, as described in Section 35.5, for each tree of each forest. Consequently, all the basic operations needed to implement edge insertions and deletions can be supported in O(log n) time. In addition to inserting and deleting edges from a forest, ET-trees must also support operations such as finding the tree of a forest that contains a given vertex, computing the size of a tree, and, more importantly, finding tree edges of level R in Tv and non-tree edges of level R incident to Tv . This can be done by augmenting the ET-trees with a constant amount of information per node: we refer the interested reader to [22] for details.

Using an amortization argument based on level changes, the claimed O(log2 n) bound on the update time can be finally proved. Namely, inserting an edge costs O(log n), as well as increasing its level. Since this can happen O(log n) times, the total amortized insertion cost, inclusive of level increases, is O(log2 n). With respect to edge deletions, cutting and linking O(log n) forest has a total cost O(log2 n); moreover, there are O(log n) recursive calls to Replace, each of cost O(log n) plus the cost amortized over level increases. The ET-trees over F0 = F allows it to answer connectivity queries in O(log n) worst-case time. As shown in [22], this can be reduced to O(log n/ log log n) by using a Θ(log n)-ary version of ET-trees.

THEOREM 36.9 (Holm et al. [22]) A dynamic graph G with n vertices can be main- tained upon insertions and deletions of edges using O(log2 n) amortized time per update and answering connectivity queries in O(log n/ log log n) worst-case running time.