Dynamic Graphs:Minimum Spanning Tree

Minimum Spanning Tree

One of the most studied dynamic problem on undirected graphs is the fully dynamic mini- mum spanning tree problem, which consists of maintaining a minimum spanning forest of a graph during insertions of edges, deletions of edges, and edge cost changes. In this section, we show that a few simple changes to the connectivity algorithm presented in Section 36.4 are sufficient to maintain a minimum spanning forest of a weighted undirected graph upon deletions of edges [22]. A general reduction from [19] can then be applied to make the deletions-only algorithm fully dynamic.

Deletions in O(log2 n) Time

In addition to starting from a minimum spanning forest, the only change concerns function Replace, that should be implemented so as to consider candidate replacement edges of level R in order of increasing weight, and not in arbitrary order. To do so, the ET-trees described in Section 35.5 can be augmented so that each node maintains the minimum weight of a non-tree edge incident to the Euler tour segment below it. All the operations can still be supported in O(log n) time, yielding the same time bounds as for connectivity.

We now discuss the correctness of the algorithm. In particular, function Replace returns a replacement edge of minimum weight on the highest possible level: it is not immediate that such a replacement edge has the minimum weight among all levels. This can be proved by first showing that the following invariant, proved in [22], is maintained by the algorithm:

Invariant (3): Every cycle C has a non-tree edge of maximum weight and minimum level among all the edges in C.

Invariant (3) can be used to prove that, among all the replacement edges, the lightest edge is on the maximum level. Let e1 and e2 be two replacement edges with w(e1) < w(e2), and let Ci be the cycle induced by ei in F , i = 1, 2. Since F is a minimum spanning forest, ei has maximum weight among all the edges in Ci. In particular, since by hypothesis w(e1) < w(e2), e2 is also the heaviest edge in cycle C = (C1 ∪ C2) \ (C1 ∩ C2). Thanks to Invariant (3), e2 has minimum level in C, proving that R(e2) ≤ R(e1). Thus, considering non-tree edges from higher to lower levels is correct.

LEMMA 36.5 (Holm et al. [22]) There exists a deletions-only minimum spanning forest algorithm that can be initialized on a graph with n vertices and m edges and supports any sequence of edge deletions in O(m log2 n) total time.

Updates in O(log4 n) Time

The reduction used to obtain a fully dynamic algorithm, which involves the top tree data structure discussed in Section 35.4, is a slight generalization of the construction proposed by Henzinger and King [19], and works as follows.

LEMMA 36.6 [19, 22] Suppose we have a deletions-only minimum spanning tree algorithm that, for any k and l, can be initialized on a graph with k vertices and l edges and supports any sequence of Ω(l) deletions in total time O(l·t(k, l)), where t is a non-decreasing function. Then there exists a fully-dynamic minimum spanning tree algorithm for a graph with n nodes starting with no edges, that, for m edges, supports updates in time

We refer the interested reader to references [19] and [22] for the description of the construction that proves Lemma 36.6. From Lemma 36.5 we get t(k, l) = O(log2 k). Hence, combining Lemmas 36.5 and 36.6, we get the claimed result.

THEOREM 36.10 (Holm et al. [22]) There exists a fully-dynamic minimum spanning forest algorithm that, for a graph with n vertices, starting with no edges, maintains a minimum spanning forest in O(log4 n) amortized time per edge insertion or deletion.