5 \chapter{Dynamic Spanning Trees}\id{dynchap}%
7 \section{Dynamic graph algorithms}
9 In many applications, we often need to solve a~certain graph problem for a~sequence of graphs that
10 differ only a~little, so recomputing the solution for every graph from scratch would be a~waste of
11 time. In such cases, we usually turn our attention to \df{dynamic graph algorithms.} A~dynamic
12 algorithm is in fact a~data structure that remembers a~graph. It offers operations that modify the
13 structure of the graph and also operations that query the result of the problem for the current
14 state of the graph. A~typical example of a~problem of this kind is dynamic maintenance of connected
17 \problemn{Dynamic connectivity}
18 Maintain an~undirected graph under a~sequence of the following operations:
20 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
21 The structure could support dynamic addition and removal of vertices, too,
22 but this is easy to add and infrequently used, so we will rather keep the set
23 of vertices fixed for clarity.}
24 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
25 identifier. This assumes that the edge did not exist yet.
26 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
27 \:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
31 We have already encountered a~special case of dynamic connectivity when implementing the
32 Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
33 any edges from the graph, which makes the problem substantially easier. This special
34 case is customarily called an~\df{incremental} or \df{semidynamic} graph algorithm.
35 We mentioned the Disjoint Set Union data structure of Tarjan (Theorem \ref{dfu})
36 which can be used for that: Connected components are represented by equivalence classes.
37 Queries on connectedness translate to \<Find>, edge insertions to \<Find>
38 followed by \<Union> if the new edge joins two different components. This way,
39 a~sequence of $m$~operations starting with an~empty graph on $n$~vertices is
40 processed in time $\O(n+m\timesalpha(m,n))$ and this holds even for the Pointer
41 Machine. Fredman and Saks \cite{fredman:cellprobe} have proven a~matching lower
42 bound in the cell-probe model which is stronger than RAM with $\O(\log n)$-bit
46 In this chapter, we will focus on the dynamic version of the minimum spanning forest.
47 This problem seems to be intimately related to the dynamic connectivity. Indeed, all known
48 algorithms for dynamic connectivity maintain some sort of a~spanning forest. For example, in the
49 incremental algorithm we have just mentioned, this forest is formed by the edges that have
50 triggered the \<Union>s. This suggests that a~dynamic MSF algorithm could be obtained by modifying
51 the mechanics of the data structure to keep the forest minimum. This will really turn out to be true, although we cannot
52 be sure that it will lead to the most efficient solution possible --- as of now, the known lower
55 Incremental MST will be easy to achieve even in the few pages of this section, but making it fully
56 dynamic will require more effort, so we will review some of the required building blocks before
59 We however have to answer one important question first: What should be the output of
60 our MSF data structure? Adding an~operation that returns the MSF of the current
61 graph would be of course possible, but somewhat impractical as this operation would have to
62 spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
63 be making the \<Insert> and \<Delete> operations report the list of modifications
64 of the MSF implied by the change in the graph.
66 Let us see what happens when we \<Insert> an~edge~$e$ to a~graph~$G$ with its minimum spanning
67 forest~$F$, obtaining a~new graph~$G'$ with its MSF~$F'$. If $e$~connects two components of~$G$ (and
68 therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the following cases happens:
69 Either $e$~is $F$-heavy and thus the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
70 and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
72 Correctness of the former case follows immediately from the Minimality Theorem (\ref{mstthm}),
73 because any $F'$-light would be also $F$-light, which is impossible as $F$~was
74 minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
75 on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
76 (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$
77 of~$F$ that contains both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
78 apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest in the cut~$\delta_G(T_1)$
79 and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
81 A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
82 an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
83 the new components (again the Blue lemma in action). If there is no such
84 replacement edge, we have deleted a~bridge, so the MSF has to remain
87 The idea of reporting differences in the MSF indeed works very well. We can summarize
88 what we have shown by the following lemma and use it to define the dynamic MSF.
91 An~\<Insert> or \<Delete> of an~edge in~$G$ causes at most one edge addition, edge
92 removal or edge exchange in $\msf(G)$.
94 \problemn{Dynamic minimum spanning forest}
95 Maintain an~undirected graph with distinct weights on edges (drawn from a~totally ordered set)
96 and its minimum spanning forest under a~sequence of the following operations:
98 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
99 \:$\<Insert>(G,u,v,w)$ --- Insert an~edge $uv$ of weight~$w$ to~$G$. Return its unique
100 identifier and the list of additions and deletions of edges in $\msf(G)$.
101 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
102 Return the list of additions and deletions of edges in $\msf(G)$.
105 \paran{Incremental MSF}%
106 To obtain an~incremental MSF algorithm, we need to keep the forest in a~data structure that
107 supports search for the heaviest edge on the path connecting a~given pair
108 of vertices. This can be handled efficiently by the Link-Cut trees of Sleator and Tarjan:
110 \thmn{Link-Cut Trees, Sleator and Tarjan \cite{sleator:trees}}\id{sletar}%
111 There is a~data structure that represents a~forest of rooted trees on~$n$ vertices.
112 Each edge of the forest has a~weight drawn from a~totally ordered set. The structure
113 supports the following operations in time $\O(\log n)$ amortized:\foot{%
114 The Link-Cut trees can offer a~plethora of other operations, but we do not mention them
115 as they are not needed for our problem.}
117 \:$\<Parent>(v)$ --- Return the parent of~$v$ in its tree or \<null> if $v$~is a~root.
118 \:$\<Root>(v)$ --- Return the root of the tree containing~$v$.
119 \:$\<Weight>(v)$ --- Return the weight of the edge $(\<Parent(v)>,v)$.
120 \:$\<PathMax>(v)$ --- Return the vertex~$u$ closest to $\<Root>(v)$ such that the edge
121 $(\<Parent>(u),u)$ is the heaviest of those on the path from the root to~$v$.
122 If more edges have the maximum weight, break the tie arbitrarily.
123 If there is no such edge ($v$~is the root itself), return \<null>.
124 \:$\<Link>(u,v,w)$ --- Connect the trees containing $u$ and~$v$ by an~edge $(u,v)$ of
125 weight~$w$. Assumes that $v~$is a tree root and $u$~lies in a~different tree.
126 \:$\<Cut>(v)$ --- Split the tree containing the non-root vertex $v$ to two trees by
127 removing the edge $(\<Parent>(v),v)$. Returns the weight of this edge.
128 \:$\<Evert>(v)$ --- Modify the orientations of edges to make~$v$ the root of its tree.
131 %% \>Additionally, all edges on the path from~$v$ to $\<Root>(v)$ can be enumerated in
132 %% time $\O(\ell + \log n)$, where $\ell$~is the length of that path. This operation
133 %% (and also the path itself) is called $\<Path>(v)$.
135 %% \>If the weights are real numbers (or in general an~arbitrary group), the $\O(\log n)$
136 %% operations also include:
139 %% \:$\<PathWeight>(v)$ --- Return the sum of the weights on $\<Path>(v)$.
140 %% \:$\<PathUpdate>(v,x)$ --- Add~$x$ to the weights of all edges on $\<Path>(v)$.
144 See \cite{sleator:trees}.
147 Once we have this structure, we can turn our ideas on updating of the MSF to
148 an~incremental algorithm:
150 \algn{\<Insert> in an~incremental MSF}
152 \algin A~graph~$G$ with its MSF $F$ represented as a~Link-Cut forest, an~edge~$uv$
153 with weight~$w$ to be inserted.
154 \:$\<Evert>(u)$. \cmt{$u$~is now the root of its tree.}
155 \:If $\<Root>(v) \ne u$: \cmt{$u$~and~$v$ lie in different trees.}
156 \::$\<Link>(v,u,w)$. \cmt{Connect the trees.}
157 \::Return ``$uv$ added''.
158 \:Otherwise: \cmt{both are in the same tree}
159 \::$y\=\<PathMax>(v)$.
160 \::$x\=\<Parent>(y)$. \cmt{Edge~$xy$ is the heaviest on $F[uv]$.}
161 \::If $\<Weight>(y) > w$: \cmt{We have to exchange~$xy$ with~$uv$.}
162 \:::$\<Cut>(y)$, $\<Evert>(v)$, $\<Link>(u,v,w)$.
163 \:::Return ``$uv$~added, $xy$~removed''.
164 \::Otherwise return ``no changes''.
165 \algout The list of changes in~$F$.
168 \thmn{Incremental MSF}
169 When only edge insertions are allowed, the dynamic MSF can be maintained in time $\O(\log n)$
170 amortized per operation.
173 Every \<Insert> performs $\O(1)$ operations on the Link-Cut forest, which take
174 $\O(\log n)$ each by Theorem \ref{sletar}.
178 We can easily extend the semidynamic MSF algorithm to allow an~operation commonly called
179 \<Backtrack> --- removal of the most recently inserted edge. It is sufficient to keep the
180 history of all MSF changes in a~stack and reverse the most recent change upon backtrack.
182 What are the obstacles to making the structure fully dynamic?
183 Deletion of edges that do not belong to the MSF is trivial (we do not
184 need to change anything) and so is deletion of bridges (we just remove the bridge
185 from the Link-Cut tree, knowing that there is no edge to replace it). The hard part
186 is the search for replacement edges after an~edge belonging to the MSF is deleted.
188 This very problem also has to be solved by algorithms for fully dynamic connectivity,
189 we will take a~look at them first.
191 %--------------------------------------------------------------------------------
193 \section{Eulerian Tour trees}
195 An~important stop on the road to fully dynamic algorithms has the name \df{Eulerian Tour trees} or
196 simply \df{ET-trees}. It is a~representation of forests introduced by Henzinger and King
197 \cite{henzinger:randdyn} in their randomized dynamic algorithms. It is similar to the Link-Cut
198 trees, but it is much simpler and instead of path operations it offers efficient operations on
199 subtrees. It is also possible to attach auxiliary data to vertices and edges of the original tree.
202 Let~$T$ be a~rooted tree. We will call a~sequence of vertices of~$T$ its \df{Eulerian Tour sequence (ET-sequence)}
203 if it lists the vertices visited by the depth-first traversal of~$T$.
204 More precisely, it can be generated by the following procedure $\<ET>(v)$
205 when it is invoked on the root of the tree:
207 \:Record~$v$ in the sequence.
208 \:For each son~$w$ of~$v$:
212 \>A~single tree can have multiple ET-sequences, corresponding to different orders in which the
213 sons can be enumerated in step~2.
215 In every ET-sequence, one of the occurrences of each vertex is defined as its \df{active occurrence} and
216 it will be used to store auxiliary data associated with that vertex.
219 An~ET-sequence contains a~vertex of degree~$d$ exactly $d$~times except for the root which
220 occurs $d+1$ times. The whole sequence therefore contains $2n-1$ elements. It indeed describes the
221 order of vertices on an~Eulerian tour in the tree with all edges doubled. Let us observe what happens
222 to an~ET-sequence when we modify the tree. (See the picture.)
224 When we \em{delete} an~edge $uv$ from the tree~$T$ (let $u$~be the parent of~$v$), the sequence
225 $AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two sequences $AuC$ and $vBv$.
226 If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence
227 transforms from $AuvuC$ to $AuC$ and $v$~alone.
229 \em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes its ET-sequence from $vAwBwCv$ to $wBwCvAw$.
230 If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
231 the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
233 \em{Joining} the roots of two trees by a~new edge makes their ET-sequences $vAv$ and~$wBw$
234 combine to $vAvwBwv$. Again, we have to handle the cases when $v$ or~$w$ has degree~1 separately:
235 $v$~and~$wBw$ combine to $vwBwv$, and $v$~with~$w$ makes $vwv$.
237 \float{\valign{\vfil#\vfil\cr
238 \hbox{\epsfbox{pic/ettree.eps}}\cr
239 \noalign{\qquad\quad}
241 $T_1: 0121034546474308980$,~~$T_2: aba$. \cr
242 $T_1-34: 01210308980, 4546474$. \cr
243 $T_1\hbox{~rooted at~3}: 3454647430898012103$. \cr
244 $T_1+0a+T_2$: $0121034546474308980aba0$. \cr
246 }}{Trees and their ET-sequences}
248 If any of the occurrences that we have removed from the sequence was active, there is always
249 a~new occurrence of the same vertex that can stand in its place and inherit the auxiliary data.
252 The ET-trees will store the ET-sequences as $(a,b)$-trees with the parameter~$a$ set upon
253 initialization of the structure and with $b=2a$. We know from the standard theorems of $(a,b)$-trees
254 (see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$
255 and that all basic operations including insertion, deletion, search, splitting and joining the trees
256 run in time $\O(b\log_a n)$ in the worst case.
258 We will use the ET-trees to maintain a~spanning forest of the dynamic graph. The auxiliary data of
259 each vertex will hold a~list of edges incident with the given vertex, that do not lie in the
260 forest. Such edges are usually called the \df{non-tree edges.}
263 \df{Eulerian Tour trees (ET-trees)} are a~data structure that represents a~forest of trees and a~set of non-tree
264 edges associated with the vertices of the forest. To avoid confusion, we will distinguish between
265 \df{original} vertices and edges (of the given trees) and the vertices and edges of the
266 data structure. The structure consists of:
268 \:A~collection of $(a,b)$-trees of some fixed parameters $a$ and~$b$.
269 Each such tree corresponds to one of the original trees~$T$. Its
270 leaves (in the usual tree order) correspond to the elements
271 of an~ET-sequence for~$T$. Each two consecutive leaves $u$ and~$v$ are separated
272 by a~unique key stored in an~internal vertex of the $(a,b)$-tree. This key is used to represent
273 the original edge~$uv$. Each original edge is therefore kept in both its orientations.
274 \:Mappings \<act>, \<edge> and \<twin>:
276 \:$\<act>(v)$ maps each original vertex to the leaf containing its active occurrence;
277 \:$\<edge>(e)$ of an~original edge~$e$ is one of the internal keys representing~it;
278 \:$\<twin>(k)$ pairs an~internal key~$k$ with the other internal key of the same original edge.
280 \:A~list of non-tree edges placed in each leaf. The lists are allowed to be non-empty only
281 in the leaves that represent active occurrences of original vertices.
282 \:Boolean \df{markers} in the internal vertices that signal presence of a~non-tree
283 edge anywhere in the subtree rooted at the internal vertex.
284 \:Counters $\<leaves>(v)$ that contain the number of leaves in the subtree rooted at~$v$.
288 The ET-trees support the following operations on the original trees:
290 \:\<Create> --- Create a~single-vertex tree.
291 \:$\<Link>(u,v)$ --- Join two different trees by an~edge~$uv$ and return a~unique identifier
293 \:$\<Cut>(e)$ --- Split a~tree by removing the edge~$e$ given by its identifier.
294 \:$\<Connected>(u,v)$ --- Test if the vertices $u$ and~$v$ lie in the same tree.
295 \:$\<Size>(v)$ --- Return the number of vertices in the tree containing the vertex~$v$.
296 \:$\<InsertNontree>(v,e)$ --- Add a~non-tree edge~$e$ to the list at~$v$ and return a~unique
297 identifier of this edge.
298 \:$\<DeleteNontree>(e)$ --- Delete a~non-tree edge~$e$ given by its identifier.
299 \:$\<ScanNontree>(v)$ --- Return a~list of non-tree edges associated with the vertices
304 We will implement the operations on the ET-trees by translating the intended changes of the
305 ET-sequences to operations on the $(a,b)$-trees. The role of identifiers of the original vertices
306 and edges will be of course played by pointers to the respective leaves and internal keys of
309 \<Cut> of an~edge splits the $(a,b)$-tree at both internal keys representing the given edge
310 and joins them back in the different order.
312 \<Link> of two trees can be accomplished by making both vertices the roots of their trees first
313 and joining the roots by an~edge afterwards. Re-rooting involves splits and joins of $(a,b)$-trees.
314 As we can split at any occurrence of the new root vertex, we will use the active occurrence
315 which we remember. Linking of the roots is translated to joining of the $(a,b)$-trees.
317 \<Connected> follows parent pointers from both $u$ and~$v$ to the roots of their trees.
318 Then it checks if the roots are equal.
320 \<Size> finds the root~$r$ and returns $\<leaves>(r)$.
322 \<InsertNontree> finds the leaf $\<act>(v)$ containing the list of $v$'s non-tree edges
323 and inserts the new edge there. The returned identifier will consist from the pointer to
324 the edge and the vertex in whose list it is stored. Then we have to recalculate the markers
325 on the path from $\<act>(v)$ to the root. \<DeleteNontree> is analogous.
327 Whenever any other operation changes a~vertex of the tree, it will also update its marker and
328 counter and, if necessary, the markers and counters on the path to the root.
330 \<ScanNontree> traverses the tree recursively from the root, but it does not enter the
331 subtrees whose roots are not marked.
333 Analysis of time complexity of the operations is now straightforward:
335 \thmn{Eulerian Tour trees, Henzinger and Rauch \cite{henzinger:randdyn}}\id{etthm}%
336 The ET-trees perform the operations \<Link> and \<Cut> in time $\O(a\log_a n)$, \<Create>
337 in $\O(1)$, \<Connected>, \<Size>, \<InsertNontree>, and \<DeleteNontree> in $\O(\log_a n)$, and
338 \<ScanNontree> in $\O(a\log_a n)$ per edge reported. Here $n$~is the number of vertices
339 in the original forest and $a\ge 2$ is an~arbitrary constant.
342 We set $b=2a$. Our implementation performs $\O(1)$ operations on the $(a,b)$-trees
343 per operation on the ET-tree, plus $\O(1)$ other work. We apply the standard theorems
344 on the complexity of $(a,b)$-trees \cite{clrs}.
347 \examplen{Connectivity acceleration}\id{accel}%
348 In most cases, the ET-trees are used with $a$~constant, but sometimes choosing~$a$ as a~function
349 of~$n$ can also have its beauty. Suppose that there is a~data structure which maintains an~arbitrary
350 spanning forest of a~dynamic graph. Suppose also that the structure works in time $\O(\log^k n)$
351 per operation and that it reports $\O(1)$ changes in the spanning forest for every change
352 in the graph. If we keep the spanning forest in ET-trees with $a=\log n$, the updates of the
353 data structure cost an~additional $\O(\log^2 n / \log\log n)$, but connectivity queries accelerate to $\O(\log
356 \paran{ET-trees with weights}
357 In some cases, we will also need a~representation of weighted graphs and enumerate the non-tree
358 edges in order of their increasing weights (in fact, it will be sufficient to find the
359 lightest one, remove it and iterate). This can be handled by a~minute modification of the
362 The tree edges will remember their weight in the corresponding internal keys of the ET-tree.
363 We replace each list of non-tree edges by an~$(a,b)$-tree keeping the edges sorted by weight.
364 We also store the minimum element of that tree separately, so that it can be accessed in constant
365 time. The boolean \em{marker} will then become the minimum weight of a~non-tree edge attached to the
366 particular subtree, which can be recalculated as easy as the markers can. Searching for the
367 lightest non-tree edge then just follows the modified markers.
369 The time complexities of all operations therefore remain the same, with a~possible
370 exception of the operations on non-tree edges, to which we have added the burden of
371 updating the new $(a,b)$-trees. This however consists of $\O(1)$ updates per a~single
372 call to \<InsertNontree> or \<DeleteNontree>, which takes $\O(a\log_a n)$ time only.
373 We can therefore conclude:
375 \corn{Weighted ET-trees}\id{wtet}%
376 In weighted ET-trees, the operations \<InsertNontree> and \<DeleteNontree> have time
377 complexity $\O(a\log_a n)$. All other operations take the same time as in Theorem
381 %--------------------------------------------------------------------------------
383 \section{Dynamic connectivity}
385 The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
386 has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and
387 $\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
388 updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
389 were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
390 A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
391 The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
392 de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.
394 The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
395 which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
396 edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
397 Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
398 replacement among the non-tree edges.
400 To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
401 L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
402 of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
403 We will maintain the following \em{invariants:}
406 \def\iinv{{\bo I\the\itemcount~}}
408 \:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
409 if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
410 \:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
411 (This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
416 At the beginning, the graph contains no edges, so both invariants are trivially
417 satisfied. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.
419 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
420 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
421 smaller one. We will try to find the replacement edge of the highest possible
422 level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
423 a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According
424 to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
425 at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can increase the levels
426 of all edges of~$T_1$ without violating either invariant.
428 We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
429 is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
430 whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
431 edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
432 will be the grist for the mill of our amortization argument: We can charge most of the work at level
433 increases and we know that the level of each edge can reach at most~$L$.)
435 If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
436 lower level and so on. If there is no replacement edge at level~0, the tree~$T$
437 remains disconnected.
440 For each level, we will use a~separate ET-tree ${\cal E}_\ell$ with~$a$ set to~2,
441 which will represent the forest~$F_i$ and the non-tree edges at that particular level.
442 Besides operations on the non-tree edges, we also need to find the tree edges of level~$\ell$
443 when we want to bring them one level up. This can be accomplished either by modifying the ET-trees
444 to attach two lists of edges attached to vertices instead of one, or by using a~second ET-tree.
446 \algn{Insertion of an~edge}
448 \algin An~edge $uv$ to insert.
450 \:Ask the ET-tree ${\cal E}_0$ if $u$ and~$v$ are in the same component. If they are:
451 \::Add $uv$ to the list of non-tree edges in ${\cal E}_0$ at both $u$ and~$v$.
453 \::Add $uv$ to~$F_0$.
456 \algn{Deletion of an~edge}
458 \algin An~edge $uv$ to delete.
459 \:$\ell \= \ell(uv)$.
460 \:If $uv$ is a~non-tree edge:
461 \::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$.
463 \::Remove $uv$ from~$F_\ell$ and hence also from $F_0,\ldots,F_{\ell-1}$.
464 \::Call $\<Replace>(uv,\ell)$ to get the replacement edge~$f$.
465 \::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$.
468 \algn{$\<Replace>(uv,i)$ -- Search for replacement for edge~$uv$ at level~$i$}
470 \algin An~edge~$uv$ to replace and a~level~$i$ such that there is no replacement
471 at levels greater than~$i$.
472 \:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively.
473 \:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$.
474 \:Find all level~$i$ edges in~$T_1$ using ${\cal E}_i$ and move them to level~$i+1$.
475 \:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
476 For each edge~$xy$, $x\in T_1$, do:
477 \::If $y\in T_2$, remove~$xy$ from~${\cal E}_i$ and return it to the caller.
478 \::Otherwise increase $\ell(xy)$ by one.
480 This includes deleting~$xy$ from~${\cal E}_i$ and inserting it to~${\cal E}_{i+1}$.
481 \:If $i>0$, call $\<Replace>(xy,i-1)$.
482 \:Otherwise return \<null>.
483 \algout The replacement edge.
486 \>As promised, time complexity will be analysed by amortization on the levels.
488 \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
489 Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per
490 \<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
494 The direct cost of an~\<Insert> is $\O(\log n)$ for the operations on the ET-trees
495 (by Theorem \ref{etthm}). We will also have the insertion pre-pay all level increases of the new
496 edge. Since the levels never decrease, each edge can be brought a~level up at most
497 $L=\lfloor\log n\rfloor$ times. Every increase costs $\O(\log n)$ on the ET-tree
498 operations, so we pay $\O(\log^2 n)$ for all of them.
500 A~\<Delete> costs $\O(\log^2 n)$ directly, as we might have to update all~$L$
501 ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization of
502 \<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
505 To bring the complexity of the operation \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
506 we apply the trick from Example \ref{accel} and store~$F_0$ in a~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
507 This does not hurt the complexity of insertions and deletions, but allows for faster queries.
511 An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity
512 problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell
513 probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm
514 \cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and
515 $\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims
516 that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations,
517 so it does not fit the definition of the PM we use. The algorithm only does not
518 need direct indexing of arrays.) So far, it is not known how to extend this algorithm
519 to fit our needs, so we omit the details.
521 %--------------------------------------------------------------------------------
523 \section{Dynamic spanning forests}\id{dynmstsect}%
525 Let us turn our attention back to the dynamic MSF now.
526 Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
527 algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
528 have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
529 operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved
530 the decremental version of the problem first (which starts with a~given graph and only edge deletions
531 are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
532 We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
533 the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
534 in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
536 \paran{Decremental MSF}%
537 Turning the algorithm from the previous section to the decremental MSF requires only two
538 changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
539 graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
540 MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
541 the lightest possible choice. We will therefore use the weighted version of the ET-trees (Corollary \ref{wtet})
542 and scan the lightest non-tree edge incident with the examined tree first. We must ensure
543 that the lower levels cannot contain a~lighter replacement edge, but fortunately the
544 light edges tend to ``bubble up'' in the hierarchy of levels. This can be formalized as
545 the following invariant:
548 \def\iinv{{\bo I\the\itemcount~}}
551 \:On every cycle, the heaviest edge has the smallest level.
555 \>This immediately implies that we always select the right replacement edge:
558 Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
559 edges for~$e$, the lightest one is at the maximum level.
562 Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle
563 rule (Lemma \ref{redlemma}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
564 In a~moment, we will show that the symmetric difference~$C$ of these two cycles is again a~cycle.
565 This implies that if $f_1$ is heavier than~$f_2$, then $f_1$~is the heaviest edge on~$C$, so
566 $\ell(f_1) \le \ell(f_2)$ by I3. Therefore the lightest of all replacement edges must have
570 Let $F^a$ and~$F^b$ be the trees of~$F-e$ in which the endpoints of~$e$ lie, and for
571 every edge~$g$ going between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints.
572 We know that $C_i$ consists of the path $F[f_i^a,e^a]$, the edge~$e$, the path $F[e^b,f_i^b]$,
573 and the edge~$f_i$. Thus~$C$ must contain the paths $F[f_1^a,f_2^a]$ and $F[f_1^b,f_2^b]$ and
574 the edges $f_1$ and~$f_2$, which together form a~simple cycle.
577 We now have to make sure that the additional invariant is indeed observed:
580 After every operation, the invariant I3 is satisfied.
583 When the structure is freshly initialized, I3 is obviously satisfied, as all edges
584 are at level~0. Sole deletions of edges (both tree and non-tree) cannot violate I3, so we need
585 to check only the replaces, in particular the place when an~edge~$e$ gets its level increased.
587 For the violation to happen for the first time, $e$~must be the heaviest on
588 some cycle~$C$, so by the Cycle rule, $e$~must be non-tree. The increase of
589 $\ell(e)$ must therefore take place when~$e$ is considered as a~replacement
590 edge incident with some tree~$T_1$ at level $\ell=\ell(e)$. We will pause the
591 computation just before this increase and we will prove that all other edges
592 of~$C$ already are at levels greater than~$\ell$, so the violation cannot occur.
594 Let us first show this for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself
595 already are at the higher levels as they were moved there at the very beginning of the
596 search for the replacement edge. The other tree edges incident with~$T_1$ would have
597 lower levels, which is impossible since the invariant would be already violated.
598 Non-tree edges of~$C$ incident with~$T_1$ are lighter than~$e$, so they were already considered
599 as~candidates for the replacement edge, because the algorithm always picks the lightest
600 candidate first. Such edges therefore have been already moved a~level up.
602 The case of edges of~$C$ that do not touch~$T_1$ is easy to handle: Such edges do not exist.
603 If they did, at least one more edge of~$C$ besides~$e$ would have to connect~$T_1$ with the other
604 trees of level~$\ell$. We already know that this could not be a~tree edge. If it were a~non-tree
605 edge, it could not have level greater than~$\ell$ by~I1 nor smaller than~$\ell$ by~I3. Therefore
606 it would be a~level~$\ell$ edge lighter than~$e$, and as such it would have been selected as the
607 replacement edge before $e$~was.
612 \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
613 When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of
614 edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then
615 updated in time $\O(\log^2 n)$ amortized per operation.
617 \paran{Fully dynamic MSF}%
618 The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
619 reduction whose properties are summarized in the following theorem:
621 \thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
622 Suppose that we have a~decremental MSF algorithm with the following properties:
624 \:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
625 \:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
627 \>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
628 with no edges, that performs $m$~insertions and deletions in amortized time:
630 \O\left( \log^3 n + \sum_{i=1}^{\log m} \sum_{j=1}^i \; t(\min(n,2^j), 2^j) \right) \hbox{\quad per operation.}
634 The reduction is very technical, but its essence is the following: We maintain a~logarithmic number
635 of decremental structures $A_0,\ldots,A_{\lfloor\log n\rfloor}$ of exponentially increasing sizes. Every non-tree
636 edge is contained in exactly one~$A_i$, tree edges can belong to multiple structures.
638 When an~edge is inserted, we union it with some of the $A_i$'s, build a~new decremental structure
639 and amortize the cost of the build over the insertions. Deletes of non-tree edges are trivial.
640 Delete of a~non-tree edge is performed on all $A_i$'s containing it and the replacement edge is
641 sought among the replacement edges found in these structures. The unused replacement edges then have
642 to be reinserted back to the structure.
644 The original reduction of Henzinger et al.~\cite{henzinger:twoec} handles these reinserts by a~mechanism of batch insertions
645 supported by their decremental structure, which is not available in our case. Holm et al.~have
646 replaced it by a~system of auxiliary edges inserted at various places in the structure.
647 We refer to the article \cite{holm:polylog} for details.
650 \corn{Fully dynamic MSF}\id{dynmsfcorr}%
651 There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized
652 per operation for graphs on $n$~vertices.
655 Apply the reduction from the previous theorem to the decremental algorithm we have
656 developed. This results in an~algorithm of amortized complexity $\O(\log^4\max(m,n))$ where~$m$
657 is the number of operations performed. This could exceed $\O(\log^4 n)$ if
658 $m$~is very large, but we can rebuild the whole structure after $n^2$~operations,
659 which brings $\log m$ down to $\O(\log n)$. The $\O(n^2\log^4 n)$ cost of the
660 rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation.
664 The limitation of MSF structures based on the Holm's algorithm for connectivity
665 to only edge deletions seems to be unavoidable. The invariant I3 could be easily
666 broken for many cycles at once whenever a~very light non-tree edge is inserted.
667 We could try increasing the level of the newly inserted edge, but we would quite
668 likely hit I1 before we managed to skip the levels of all the heaviest edges on the
671 On the other hand, if we decided to drop I3, we would encounter different problems. The ET-trees can
672 bring the lightest non-tree incident with the current tree~$T_1$, but the lightest replacement edge
673 could also be located in the super-trees of~$T_1$ at the lower levels, which are too large to scan
674 and both I1 and I2 prevent us from charging the time on increasing levels there.
676 An~interesting special case in which insertions are possible is when all non-tree
677 edges have the same weight. This leads to the following algorithm for dynamic MSF
678 on~graphs with a~small set of allowed edge weights. It is based on an~idea similar
679 to the $\O(k\log^3 n)$ algorithm of Henzinger and King \cite{henzinger:randdyn},
680 but adapted to use the better results on dynamic connectivity we have at hand.
682 \paran{Dynamic MSF with limited edge weights}%
683 Let us assume for a~while that our graph has edges of only two different weights (let us say
684 1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall
685 the observation in \ref{multiweight} that the basic structural properties of
686 the MST's from Section \ref{mstbasics} still hold.
688 We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge
689 weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm maintaining
690 an~arbitrary spanning forest~$F_1$ of~$G_1$, which is obviously minimum. Then we add
691 another instance~$\C_2$ to maintain a~spanning forest~$F_2$ of the graph $G_2\cup F_1$
692 such that all edges of~$F_1$ are forced to be in~$F_2$. Obviously, $F_2$~is the
693 MSF of the whole graph~$G$ --- if any edge of~$F_1$ were not contained in~$\msf(G)$,
694 we could use the standard exchange argument to create an~even lighter spanning tree.\foot{This
695 is of course the Blue lemma in action, but we have to be careful as we did not have proven it
696 for graphs with multiple edges of the same weight.}
698 When a~weight~2 edge is inserted to~$G$, we insert it to~$\C_2$ and it either enters~$F_2$
699 or becomes a~non-tree edge. Similarly, deletion of a~weight~2 edge is a~pure deletion in~$\C_2$,
700 because such edges can be replaced only by other weight~2 edges.
702 Insertion of edges of weight~1 needs more attention: We insert the edge to~$\C_1$. If~$F_1$
703 stays unchanged, we are done. If the new edge enters~$F_1$, we use Sleator-Tarjan trees
704 kept for~$F_2$ to check if the new edge covers some tree edge of weight~2. If this is not
705 the case, we insert the new edge to~$\C_2$ and hence also to~$F_2$ and we are done.
706 Otherwise we exchange one of the covered weight~2 edges~$f$ for~$e$ in~$\C_2$. We note
707 that~$e$ can inherit the level of~$f$ and $f$~can become a~non-tree edge without
708 changing its level. This adjustment can be performed in time $\O(\log^2 n)$, including
709 paying for the future level increases of the new edge.
711 Deletion of weight~1 edges is once more straightforward. We delete the edge from~$\C_1$.
712 If it has no replacement, we delete it from~$\C_2$ as well. If it has a~replacement,
713 we delete the edge from~$\C_2$ and insert the replacement on its place as described
714 above. We observe than this pair of operations causes an~insertion, deletion or
715 a~replacement in~$\C_2$.
717 This way, we can handle every insertion and deletion in time $\O(\log^2 n)$ amortized.
718 This construction can be iterated in an~obvious way: if we have $k$~distinct edge weights,
719 we build $k$~connectivity structures $\C_1,\ldots,\C_k$. The structure~$\C_i$ contains edges of
720 weight~$i$ together with the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy:
722 \thmn{MSF with limited edge weights}
723 There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
724 per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.
727 A~change in the graph~$G$ involving an~edge of weight~$w$ causes a~change in~$\C_w$,
728 which can propagate to~$\C_{w+1}$ and so on, possibly up to~$\C_k$. In each~$\C_i$,
729 we spend time $\O(\log^2 n)$ by updating the connectivity structure according to
730 Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan trees
731 by Theorem \ref{sletar}.
734 %--------------------------------------------------------------------------------
736 \section{Almost minimum trees}\id{kbestsect}%
738 In some situations, finding the single minimum spanning tree is not enough and we are interested
739 in the $K$~lightest spanning trees, usually for some small value of~$K$. Katoh, Ibaraki
740 and Mine \cite{katoh:kmin} have given an~algorithm of time complexity $\O(m\log\beta(m,n) + Km)$,
741 building on the MST algorithm of Gabow et al.~\cite{gabow:mst}.
742 Subsequently, Eppstein \cite{eppstein:ksmallest} has discovered an~elegant preprocessing step which allows to reduce
743 the running time to $\O(m\log\beta(m,n) + \min(K^2,Km))$ by eliminating edges
744 which are either present in all $K$ trees or in none of them.
745 We will show a~variant of their algorithm based on the MST verification
746 procedure of Section~\ref{verifysect}.
748 In this section, we will require the edge weights to be real numbers (or integers), because
749 comparisons are certainly not sufficient to determine the second best spanning tree. We will
750 assume that our computation model is able to add, subtract and compare the edge weights
753 Let us focus on finding the second lightest spanning tree first.
755 \paran{Second lightest spanning tree}%
756 Suppose that we have a~weighted graph~$G$ and a~sequence $T_1,\ldots,T_z$ of all its spanning
757 trees. Also suppose that the weights of these spanning trees are distinct and that the sequence
758 is ordered by weight, i.e., $w(T_1) < \ldots < w(T_z)$ and $T_1 = \mst(G)$. Let us observe
759 that each tree is similar to at least one of its predecessors:
761 \lemman{Difference lemma}\id{kbl}%
762 For each $i>1$ there exists $j<i$ such that $T_i$ and~$T_j$ differ by a~single edge exchange.
765 We know from the Monotone exchange lemma (\ref{monoxchg}) that $T_1$ can be transformed
766 to~$T_i$ by a~sequence of edge exchanges which never decreases tree weight. The last
767 exchange in this sequence therefore obtains~$T_i$ from a~tree of the desired properties.
771 This lemma implies that the second best spanning tree~$T_2$ differs from~$T_1$ by a~single
772 edge exchange. It remains to find which exchange it is. Let us consider the exchange
773 of an~edge $f\in E\setminus T_1$ with an~edge $e\in T_1[f]$. We get a~tree $T_1-e+f$
774 of weight $w(T_1)-w(e)+w(f)$. To obtain~$T_2$, we have to find~$e$ and~$f$ such that the
775 difference $w(f)-w(e)$ is the minimum possible. Thus for every~$f$, the edge $e$~must be always
776 the heaviest on the path $T_1[f]$. We can now apply the algorithm from Corollary \ref{rampeaks}
777 and find the heaviest edges (peaks) of all such paths and thus examine all possible choices of~$f$
778 in linear time. So we get:
781 For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find
782 edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum.
785 We will call this \df{finding the best exchange in $(H,T)$.}
788 Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
790 \paran{Third lightest spanning tree}%
791 Once we know~$T_1$ and~$T_2$, how to get~$T_3$? According to the Difference lemma, $T_3$~can be
792 obtained by a~single exchange from either~$T_1$ or~$T_2$. Therefore we need to find the
793 best exchange for~$T_2$ and the second best exchange for~$T_1$ and use the better of them.
794 The latter is not easy to find directly, so we will make a~minor side step.
796 We know that $T_2$ equals $T_1-e+f$ for some edges $e$ and~$f$. We define two auxiliary graphs:
797 $G_1 := G/e$ and $G_2 := G-e$. The tree~$T_1/e$ is obviously the MST of~$G_1$
798 (by the Contraction lemma) and $T_2$ is the MST of~$G_2$ (all $T_2$-light edges
799 in~$G_2$ would be $T_1$-light in~$G$).
802 The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
805 \:If $T_3 = T_1-e'+f'$ for $e'\ne e$, then $T_3/e = (T_1/e)-e'+f'$ in~$G_1$.
806 \:If $T_3 = T_1-e+f'$, then $T_3 = T_2 - f + f'$ in~$G_2$.
807 \:If $T_3 = T_2-e'+f'$, then this exchange is found in~$G_2$.
810 \>Conversely, a~single exchange in $(G_1,T_1/e)$ or in $(G_2,T_2)$ corresponds
811 to an~exchange in either~$(G,T_1)$ or $(G,T_2)$.
812 Even stronger, a~spanning tree~$T$ of~$G$ either contains~$e$ and then $T\sgc
813 e$ is a~spanning tree of~$G_1$, or $T$~doesn't contain~$e$ and so it is
814 a~spanning tree of~$G_2$.
816 Thus we can run the previous algorithm for finding the best edge exchange
817 on both~$G_1$ and~$G_2$ and find~$T_3$ again in time $\O(m)$.
819 \paran{Further spanning trees}%
820 The construction of auxiliary graphs can be iterated to obtain $T_1,\ldots,T_K$
821 for an~arbitrary~$K$. We will build a~\df{meta-tree} of auxiliary graphs. Each node of this meta-tree
822 is assigned a~graph\foot{This graph is always derived from~$G$ by a~sequence of edge deletions
823 and contractions. It is tempting to say that it is a~minor of~$G$, but this is not true as we
824 preserve multiple edges.} and its minimum spanning tree. The root node contains~$(G,T_1)$,
825 its sons have $(G_1,T_1/e)$ and $(G_2,T_2)$. When $T_3$ is obtained by an~exchange
826 in one of these sons, we attach two new leaves to that son and we assign to them the two auxiliary
827 graphs derived by contracting or deleting the exchanged edge. Then we find the best
828 edge exchanges among all leaves of the new meta-tree and repeat the process. By Observation \ref{tbobs},
829 each spanning tree of~$G$ is generated exactly once. The Difference lemma guarantees that
830 the trees are enumerated in the increasing order.
832 Recalculating the best exchanges in all leaves of the meta-tree after generating each~$T_i$
833 is of course not necessary, because most leaves stay unchanged. We will rather remember
834 the best exchange for each leaf and keep the weight differences of these exchanges in a~heap. In every step, we will
835 delete the minimum from the heap and use the exchange in the particular leaf to generate
836 a~new spanning tree. Then we will create the new leaves, calculate their best exchanges and insert
837 them into the heap. The algorithm is now straightforward and so will be its analysis:
839 \algn{Finding $K$ best spanning trees}\id{kbestalg}%
841 \algin A~weighted graph~$G$, its MST~$T_1$ and an~integer $K>0$.
842 \:$R\=$ a~meta tree whose vertices carry triples $(G',T',F')$. Initially
843 it contains just a~root with $(G,T_1,\emptyset)$.
845 \cmt{$G'$ is a~graph, $T'$~is its MST, and~$F'$ is a~set of edges of~$G$
846 that are contracted in~$G'$.}
847 \:$H\=$ a~heap of quadruples $(\delta,r,e,f)$ ordered on~$\delta$, initially empty.
849 \cmt{Each quadruple describes an~exchange of~$e$ for~$f$ in a~leaf~$r$ of~$R$ and $\delta=w(f)-w(e)$
850 is the weight gain of this exchange.}
851 \:Find the best edge exchange in~$(G,T_1)$ and insert it to~$H$.
854 \::Delete the minimum quadruple $(\delta,r,e,f)$ from~$H$.
855 \::$(G',T',F') \=$ the triple carried by the leaf~$r$.
857 \::$T_i\=(T'-e+f) \cup F'$. \cmt{The next spanning tree}
858 \::$r_1\=$ a~new leaf carrying $(G'/e,T'/e,F'+e)$.
859 \::$r_2\=$ a~new leaf carrying $(G'-e,T_i,F')$.
860 \::Attach~$r_1$ and~$r_2$ as sons of~$r$.
861 \::Find the best edge exchanges in~$r_1$ and~$r_2$ and insert them to~$H$.
862 \algout The spanning trees $T_2,\ldots,T_K$.
866 Given~$G$ and~$T_1$, we can find $T_2,\ldots,T_K$ in time $\O(Km + K\log K)$.
869 Generating each~$T_i$ requires finding the best exchange for two graphs and $\O(1)$
870 operations on the heap. The former takes $\O(m)$ according to Corollary \ref{rampeaks},
871 and each heap operation takes $\O(\log K)$.
874 \paran{Arbitrary weights}%
875 While the assumption that the weights of all spanning trees are distinct has helped us
876 in thinking about the problem, we should not forget that it is somewhat unrealistic.
877 We could refine the proof of our algorithm and demonstrate that the algorithm indeed works
878 without this assumption, but we will rather show that the ties can be broken easily.
880 Let~$\delta$ be the minimum positive difference among the weights of all spanning trees
881 of~$G$ and $e_1,\ldots,e_m$ be the edges of~$G$. We observe that it suffices to
882 increase $w(e_i)$ by~$\delta_i = \delta/2^{i+1}$. The cost of every spanning tree
883 has increased by at most $\sum_i\delta_i < \delta/2$, so if $T$~was lighter
884 than~$T'$, it still is. On the other hand, no two trees share the same
885 weight difference, so all tree weights are now distinct.
887 The exact value of~$\delta$ is not easy to calculate, but closer inspection of the algorithm
888 reveals that it is not needed at all. The only place where the edge weights are examined
889 is when we search for the best exchange. In this case, we compare the differences of
890 pairs of edge weights with each other. Each such difference is therefore adjusted
891 by $\delta\cdot(2^{-i}-2^{-j})$ for some $i,j>1$, which again does not influence comparison
892 of originally distinct differences. If two differences were identical, it is sufficient
893 to look at their values of~$i$ and~$j$, i.e., at the identifiers of the edges.
895 \paran{Invariant edges}%
896 Our algorithm can be further improved for small values of~$K$ (which seems to be the common
897 case in most applications) by the reduction of Eppstein \cite{eppstein:ksmallest}.
898 We will observe that there are many edges of~$T_1$
899 which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
900 many edges of $G\setminus T_1$ which are excluded from those spanning trees.
901 The idea is the following (again assuming that the tree weights are distinct):
904 For an~edge $e\in T_1$, we define its \df{gain} $g(e)$ as the minimum weight gained by exchanging~$e$
905 for another edge. Similarly, we define the gain $G(f)$ for $f\not\in T_1$. Put formally:
907 g(e) &:= \min\{ w(f)-w(e) \mid f\in E, e\in T[f] \} \cr
908 G(f) &:= \min\{ w(f)-w(e) \mid e\in T[f] \}.\cr
912 When $t_1,\ldots,t_{n-1}$ are the edges of~$T_1$ in order of increasing gain,
913 the edges $t_K,\ldots,t_{n-1}$ are present in all trees $T_2,\ldots,T_K$.
916 The best exchanges in~$T_1$ involving $t_1,\ldots,t_{K-1}$ produce~$K-1$ spanning trees
917 of increasing weights. Any exchange involving $t_K,\ldots,t_n$ produces a~tree
918 which is heavier or equal than all those trees. (We are ascertained by the Monotone exchange lemma
919 that the gain of such exchanges cannot be reverted by any later exchanges.)
923 When $q_1,\ldots,q_{m-n+1}$ are the edges of $G\setminus T_1$ in order of increasing gain,
924 the edges $q_K,\ldots,q_{m-n+1}$ are not present in any of $T_2,\ldots,T_K$.
927 Similar to the previous lemma.
931 It is therefore sufficient to find $T_2,\ldots,T_K$ in the graph obtained from~$G$ by
932 contracting the edges $t_K,\ldots,t_n$ and deleting $q_K,\ldots,q_{m-n+1}$. This graph
933 has only $\O(K)$ vertices and $\O(K)$ edges. The only remaining hurdle is how to
934 calculate the gains. For edges outside~$T_1$, it again suffices to find the peaks of the
935 covered paths. The gains of MST edges require a~different algorithm, but Tarjan \cite{tarjan:applpc}
936 has shown how to obtain them in time $\O(m\timesalpha(m,n))$.
938 When we put the results of this section together, we can conclude:
940 \thmn{Finding $K$ lightest spanning trees}\id{kbestthm}%
941 For a~given graph~$G$ with real edge weights and a~positive integer~$K$, the $K$~best spanning trees can be found
942 in time $\O(m\timesalpha(m,n) + \min(K^2,Km + K\log K))$.
945 First we find the MST of~$G$ in time $\O(m\timesalpha(m,n))$ using the Pettie's Optimal
946 MST algorithm (Theorem \ref{optthm}). Then we calculate the gains of MST edges by the
947 Tarjan's algorithm from \cite{tarjan:applpc}, again in $\O(m\timesalpha(m,n))$, and
948 the gains of the other edges using our MST verification algorithm (Corollary \ref{rampeaks})
949 in $\O(m)$. We use Lemma \ref{gaina} to identify edges that are required, and Lemma \ref{gainb}
950 to find edges that are superfluous. We contract the former edges, remove the latter ones
951 and run Algorithm \ref{kbestalg} to find the spanning trees. By Lemma \ref{kbestl}, it runs in
954 If~$K\ge m$, this reduction does not pay off, so we run Algorithm \ref{kbestalg}
955 directly on the input graph.
958 \paran{Improvements}%
959 It is an~interesting open question whether the algorithms of Section \ref{verifysect} can
960 be modified to calculate all gains in linear time. The main procedure could be, but it requires having
961 the input reduced to a~balance tree beforehand and here the Bor\o{u}vka trees fail. The Buchsbaum's
962 Pointer-Machine algorithm (\ref{pmverify}) seems to be more promising.
965 When $K$~is large, re-running the verification algorithm for every change of the graph
966 is too costly. Frederickson \cite{frederickson:ambivalent} has shown how to find the best
967 swaps dynamically, reducing the overall time complexity of Algorithm \ref{kbestalg}
968 to $\O(Km^{1/2})$ and improving the bound in Theorem \ref{kbestthm} to $\O(m\timesalpha(m,n)
969 + \min( K^{3/2}, Km^{1/2} ))$. It is open if the dynamic data structures of this
970 chapter could be modified to bring the complexity of finding the next tree down
973 \paran{Multiple minimum trees}%
974 Another nice application of Theorem \ref{kbestthm} is finding all minimum spanning
975 trees in a~graph that does not have distinct edge weights. We find a~single MST using
976 any of the algorithms of the previous chapters and then we use the enumeration algorithm
977 of this section to find further spanning trees as long as their weights are minimum.
979 We can even use the reduction of the number of edges from Lemmata \ref{gaina} and \ref{gainb}:
980 we start with some fixed~$K$ and when we exhaust all~$K$ trees, we double~$K$ and restart
981 the whole process. The extra time spent on these restarts is bounded by the time of the
984 This finally settles the question that we have asked ourselves in Section \ref{mstbasics},
985 namely whether we lose anything by assuming that all weights are distinct and searching
986 for the single minimum tree.