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
10 of graphs that differ only a~little, so recomputing the solution from scratch for
11 every graph would be a~waste of time. In such cases, we usually turn our attention
12 to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure
13 that remembers a~graph and offers operations that modify the structure of the graph
14 and also operations that query the result of the problem for the current state
15 of the graph. A~typical example of a~problem of this kind is dynamic
16 maintenance of connected components:
18 \problemn{Dynamic connectivity}
19 Maintain an~undirected graph under a~sequence of the following operations:
21 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
22 The structure could support dynamic addition and removal of vertices, too,
23 but this is easy to add and infrequently used, so we will rather keep the set
24 of vertices fixed for clarity.}
25 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
26 identifier. This assumes that the edge did not exist yet.
27 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
28 \:$\<Connected>(G,u,v)$ --- Test if $u$ and~$v$ are in the same connected component of~$G$.
32 We have already encountered a~special case of dynamic connectivity when implementing the
33 Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
34 any edges from the graph, which makes the problem substantially easier. This special
35 case is customarily called an~\df{incremental} or \df{semidynamic} graph algorithm.
36 We mentioned the Disjoint Set Union data structure of Tarjan and van Leeuwen (Theorem \ref{dfu})
37 which can be used for that: Connected components are represented as an~equivalence classes.
38 Queries on connectedness translate to \<Find>, edge insertions to \<Find>
39 followed by \<Union> if the new edge joins two different components. This way,
40 a~sequence of $m$~operations starting with an~empty graph on $n$~vertices is
41 processed in time $\O(n+m\timesalpha(m,n))$ and this holds even for the Pointer
42 Machine. Fredman and Saks \cite{fredman:cellprobe} have proven a~matching lower
43 bound in the cell-probe model which is stronger than RAM with $\O(\log n)$-bit
46 The edges that have triggered the \<Union>s form a~spanning forest of the current graph.
47 So far, all known algorithms for dynamic connectivity maintain some sort of a~spanning
48 tree. This suggests that a~dynamic MST algorithm could be obtained by modifying the
49 dynamic connectivity algorithms. This will indeed turn out to be true. Incremental MST
50 is easy to achieve even in the few pages of this section, but making it fully dynamic will require
51 more effort, so we will review some of the required building blocks before going into that.
53 We however have to answer one important question first: What should be the output of
54 our MSF data structure? Adding an~operation that would return the MSF of the current
55 graph is of course possible, but somewhat impractical as this operation has to
56 spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
57 be making the \<Insert> and \<Delete> operations report the list of modifications
58 of the MSF implied by the change in the graph.
60 Let us see what happens when we \<Insert> an~edge~$e$ to a~graph~$G$ with its minimum spanning
61 forest~$F$, obtaining a~new graph~$G'$ with its MSF~$F'$. If $e$~connects two components of~$G$ (and
62 therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the following cases happens:
63 Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
64 and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
66 Correctness of the former case follows immediately from the Theorem on Minimality by order
67 (\ref{mstthm}), because all $F'$-light would be also $F$-light, which is impossible as $F$~was
68 minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
69 on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
70 (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$
71 of~$F$ that contains both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
72 apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest edge of the cut~$\delta_G(T_1)$
73 and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
75 A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
76 an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
77 the new components (again the Blue lemma in action). If there is no such
78 replacement edge, we have deleted a~bridge, so the MSF has to remain
81 The idea of reporting differences in the MSF indeed works very well. We can summarize
82 what we have shown in the following lemma and use it to define the dynamic MSF.
85 An~\<Insert> or \<Delete> of an~edge in~$G$ causes at most one edge addition, edge
86 removal or edge exchange in $\msf(G)$.
88 \problemn{Dynamic minimum spanning forest}
89 Maintain an~undirected graph with distinct weights on edges (drawn from a~totally ordered set)
90 and its minimum spanning forest under a~sequence of the following operations:
92 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
93 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$. Return its unique
94 identifier and the list of additions and deletions of edges in $\msf(G)$.
95 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
96 Return the list of additions and deletions of edges in $\msf(G)$.
99 \paran{Incremental MSF}%
100 To obtain an~incremental MSF algorithm, we need to keep the forest in a~data structure that
101 supports search for the heaviest edge on the path connecting a~given pair
102 of vertices. This can be handled efficiently by the Link-Cut trees of Sleator and Tarjan:
104 \thmn{Link-Cut Trees, Sleator and Tarjan \cite{sleator:trees}}\id{sletar}%
105 There is a~data structure that represents a~forest of rooted trees on~$n$ vertices.
106 Each edge of the forest has a~weight drawn from a~totally ordered set. The structure
107 supports the following operations in time $\O(\log n)$ amortized:\foot{%
108 The Link-Cut trees offer many other operations, but we do not mention them
109 as they are not needed in our application.}
111 \:$\<Parent>(v)$ --- Return the parent of~$v$ in its tree or \<null> if $v$~is a~root.
112 \:$\<Root>(v)$ --- Return the root of the tree containing~$v$.
113 \:$\<Weight>(v)$ --- Return the weight of the edge $(\<Parent(v)>,v)$.
114 \:$\<PathMax>(v)$ --- Return the vertex~$w$ closest to $\<Root>(v)$ such that the edge
115 $(\<Parent>(w),w)$ is the heaviest of those on the path from the root to~$v$.
116 If more edges have the maximum weight, break the tie arbitrarily.
117 If there is no such edge ($v$~is the root itself), return \<null>.
118 \:$\<Link>(u,v,x)$ --- Connect the trees containing $u$ and~$v$ by an~edge $(u,v)$ of
119 weight~$x$. Assumes that $u~$is a tree root and $v$~lies in a~different tree.
120 \:$\<Cut>(v)$ --- Split the tree containing the non-root vertex $v$ to two trees by
121 removing the edge $(\<Parent>(v),v)$. Returns the weight of this edge.
122 \:$\<Evert>(v)$ --- Modify the orientations of the edges in the tree containing~$v$
123 to make~$v$ the tree's root.
126 %% \>Additionally, all edges on the path from~$v$ to $\<Root>(v)$ can be enumerated in
127 %% time $\O(\ell + \log n)$, where $\ell$~is the length of that path. This operation
128 %% (and also the path itself) is called $\<Path>(v)$.
130 %% \>If the weights are real numbers (or in general an~arbitrary group), the $\O(\log n)$
131 %% operations also include:
134 %% \:$\<PathWeight>(v)$ --- Return the sum of the weights on $\<Path>(v)$.
135 %% \:$\<PathUpdate>(v,x)$ --- Add~$x$ to the weights of all edges on $\<Path>(v)$.
139 See \cite{sleator:trees}.
142 Once we have this structure, we can turn our ideas on updating of the MSF to
143 an~incremental algorithm:
145 \algn{\<Insert> in an~incremental MSF}
147 \algin A~graph~$G$ with its MSF $F$ represented as a~Link-Cut forest, an~edge~$uv$
148 with weight~$w$ to be inserted.
149 \:$\<Evert>(u)$. \cmt{$u$~is now the root of its tree.}
150 \:If $\<Root>(v) \ne u$: \cmt{$u$~and~$v$ lie in different trees.}
151 \::$\<Link>(u,v,w)$. \cmt{Connect the trees.}
152 \::Return ``$uv$ added''.
153 \:Otherwise: \cmt{both are in the same tree}
154 \::$y\=\<PathMax>(v)$.
155 \::$x\=\<Parent>(y)$. \cmt{Edge~$xy$ is the heaviest on $F[uv]$.}
156 \::If $\<Weight>(y) > w$: \cmt{We have to exchange~$xy$ with~$uv$.}
157 \:::$\<Cut>(y)$, $\<Evert>(v)$, $\<Link>(v,y,w)$.
158 \:::Return ``$uv$~added, $xy$~removed''.
159 \::Otherwise return ``no changes''.
160 \algout The list of changes in~$F$.
163 \thmn{Incremental MSF}
164 When only edge insertions are allowed, the dynamic MSF can be maintained in time $\O(\log n)$
165 amortized per operation.
168 Every \<Insert> performs $\O(1)$ operations on the Link-Cut forest, which take
169 $\O(\log n)$ each by Theorem \ref{sletar}.
173 We can easily extend the semidynamic MSF algorithm to allow an~operation commonly called
174 \<Backtrack> --- removal of the most recently inserted edge. It is sufficient to keep the
175 history of all MSF changes in a~stack and reverse the most recent change upon backtrack.
177 What are the obstacles to making the structure fully dynamic?
178 Deletion of edges that do not belong to the MSF is trivial (we do not
179 need to change anything) and so is deletion of bridges (we just remove the bridge
180 from the Link-Cut tree, knowing that there is no edge to replace it). The hard part
181 is the search for replacement edges after an~edge of the MSF is deleted.
183 This very problem also has to be solved by algorithms for fully dynamic connectivity,
184 we will take a~look on them first.
186 %--------------------------------------------------------------------------------
188 \section{Eulerian Tour trees}
190 An~important stop on the road to fully dynamic algorithms has the name \df{Eulerian Tour trees} or
191 simply \df{ET-trees}. It is a~representation of forests introduced by Henzinger and King
192 \cite{henzinger:randdyn} in their randomized dynamic algorithms. It is similar to the one by Sleator
193 and Tarjan, but it is much simpler and instead of path operations it offers efficient operations on
194 subtrees. It is also possible to attach auxiliary data to vertices and edges of the original tree.
197 The \df{Eulerian Tour sequence} $\Eul(T)$ of a~rooted tree~$T$ is the sequence of vertices of~$T$ as visited
198 by the depth-first traversal of~$T$. More precisely, it is generated by the following algorithm $\<ET>(v)$
199 when it is invoked on the root of the tree:
201 \:Record~$v$ in the sequence.
202 \:For each son~$w$ of~$v$:
203 \::Call $\<ET>(w)$ recursively.
206 \>One of the occurrences of each vertex is defined as its \df{active occurrence} and it will
207 be used to store auxiliary data associated with the vertex.
210 The ET-sequence contains a~vertex of degree~$d$ exactly $d$~times except for the root which
211 occurs $d+1$ times. The whole sequence therefore contains $2n-1$ elements. It indeed describes the
212 order vertices on an~Eulerian tour in the tree with all edges doubled. Let us observe what happens
213 to the ET-sequence when we modify the tree.
215 When we \em{delete} an~edge $uv$ from the tree~$T$ (let $u$~be the parent of~$v$), the sequence
216 $\Eul(T) = AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two ET-sequences $AuC$ and $vBv$.
217 If there was only a~single occurrence of~$v$, it corresponded to a~leaf and thus the second
218 sequence should consist of $v$~alone.
220 \em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes $\Eul(T)$ from $vAwBwCv$ to $wBwCvAw$.
221 If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
222 the sequence $vw$ becomes $wv$. Note that this works regardless of the presence of~$w$ inside~$B$.
224 \em{Joining} the roots of two trees by a~new edge makes their ET-sequences $vAv$ and~$wBw$
225 combine to $vAvwBwv$. Again, we have to handle the cases when $v$ or~$w$ has degree~1 separately:
226 $v$~and~$wBw$ combine to $vwBwv$, and $v$~with~$w$ makes $vwv$.
228 \float{\valign{\vfil#\vfil\cr
229 \hbox{\epsfbox{pic/ettree.eps}}\cr
230 \noalign{\qquad\quad}
232 $\Eul(T_1) = 0121034546474308980$,~~$\Eul(T_2) = aba$. \cr
233 $\Eul(T_1-34) = 01210308980, 4546474$. \cr
234 $\Eul(T_1\hbox{~rooted at~3}) = 3454647430898012103$. \cr
235 $\Eul(T_1+0a+T_2)$: $0121034546474308980aba0$. \cr
237 }}{Trees and their ET-sequences}
239 If any of the occurrences that we have removed from the sequence was active, there is always
240 a~new occurrence of the same vertex that can stand in its place and inherit the auxiliary data.
242 The ET-trees will represent the ET-sequences by $(a,b)$-trees with the parameter~$a$ set upon
243 initialization of the structure and with $b=2a$. We know from the standard theorems of $(a,b)$-trees
244 (see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$
245 and that all basic operations including insertion, deletion, search, splitting and joining the trees
246 run in time $\O(a\log_a n)$ in the worst case.
248 We will use the ET-trees to maintain a~spanning forest of the current graph. The auxiliary data of
249 each vertex will hold a~list of edges incident with the given vertex, which do not lie in the
250 forest. Such edges are usually called the \df{non-tree edges.}
253 \df{Eulerian Tour trees} are a~data structure that represents a~forest of trees and a~set of non-tree
254 edges associated with the vertices of the forest. To avoid confusion, we will distinguish between
255 \df{original} vertices and edges (of the original trees) and the vertices and edges of the
256 data structure. The structure consists of:
258 \:A~collection of $(a,b)$-trees with some fixed parameters $a$ and~$b$.
259 Each such tree corresponds to one of the original trees~$T$. Its
260 leaves (in the usual tree order) correspond to the elements
261 of the ET-sequence $\Eul(T)$. Each two consecutive leaves $u$ and~$v$ are separated
262 by a~unique key stored in an~internal vertex of the $(a,b)$-tree. This key is used to represent
263 the original edge~$uv$. Each original edge is therefore kept in both its orientations.
264 \:A~mapping $\<act>(v)$ that maps each original vertex to the leaf containing its active occurrence.
265 \:A~mapping $\<edge>(e)$ that maps an~original edge~$e$ to one of the internal keys representing it.
266 \:A~mapping $\<twin>(k)$ that maps an~internal key~$k$ to the other internal key of the same
268 \:A~list of non-tree edges placed in each leaf. The lists are allowed to be non-empty only
269 in the leaves that represent active occurrences of original vertices.
270 \:Boolean \df{markers} in the internal vertices that signal presence of a~non-tree
271 edge anywhere in the subtree rooted at that internal vertex.
272 \:Counters $\<leaves>(v)$ that contain the number of leaves in the subtree rooted at~$v$.
274 \>The structure supports the following operations on the original trees:
276 \:\<Create> --- Create a~single-vertex tree.
277 \:$\<Link>(u,v)$ --- Join two different trees by an~edge~$uv$ and return a~unique identifier
279 \:$\<Cut>(e)$ --- Split a~tree by removing the edge~$e$ given by its identifier.
280 \:$\<Root>(v)$ --- Return the root of the ET-tree containing the vertex~$v$. This can be used
281 to test whether two vertices lie in the same tree. However, the root is not guaranteed
282 to stay the same when the tree is modified by a~\<Link> or \<Cut>.
283 \:$\<Size>(v)$ --- Return the number of vertices in the tree containing the vertex~$v$.
284 \:$\<InsertNontree>(v,e)$ --- Add a~non-tree edge~$e$ to the list at~$v$ and return a~unique
285 identifier of this edge.
286 \:$\<DeleteNontree>(e)$ --- Delete a~non-tree edge~$e$ given by its identifier.
287 \:$\<ScanNontree>(v)$ --- Return non-tree edges stored in the same tree as~$v$.
289 \>If the non-tree edges have weights,
292 We will implement the operations on the ET-trees by translating the intended changes of the
293 ET-sequences to operations on the $(a,b)$-trees. The role of identifiers of the original vertices
294 and edges will be of course played by pointers to the respective leaves and internal keys of
297 \<Cut> of an~edge splits the $(a,b)$-tree at both internal keys representing the given edge
298 and joins them back in the different order.
300 \<Link> of two trees can be accomplished by making both vertices the roots of their trees first
301 and joining the roots by an~edge afterwards. Re-rooting again involves splits and joins of $(a,b)$-trees.
302 As we can split at any occurrence of the new root vertex, we will use the active occurrence
303 which we remember. Joining of the roots translated to joining of the $(a,b)$-trees.
305 \<Root> just follows parent pointers in the $(a,b)$-tree and it walks the path from the leaf
308 \<Size> finds the root and returns its counter.
310 \<InsertNontree> finds the leaf $\<act>(v)$ containing the list of $v$'s non-tree edges
311 and inserts the new edge there. The returned identifier will consist from the pointer to
312 the edge and the vertex in whose list it is stored. Then we have to recalculate the markers
313 on the path from $\<act>(v)$ to the root. \<DeleteNontree> is analogous.
315 Whenever any other operation changes a~vertex of the tree, it will also update its marker and
316 counter and, if necessary, the markers and counters on the path to the root.
318 \<ScanNontree> traverses the tree recursively from the root, but it does not enter the
319 subtrees whose roots are not marked.
321 Analysis of the time complexity is now straightforward:
323 \thmn{Eulerian Tour trees, Henzinger and Rauch \cite{henzinger:randdyn}}\id{etthm}%
324 The ET-trees perform the operations \<Link> and \<Cut> in time $\O(a\log_a n)$, \<Create>
325 in $\O(1)$, \<Root>, \<InsertNontree>, and \<DeleteNontree> in $\O(\log_a n)$, and
326 \<ScanNontree> in $\O(a\log_a n)$ per edge reported. Here $n$~is the number of vertices
327 in the original forest and $a\ge 2$ is an~arbitrary constant.
330 We set $b=2a$. Our implementation performs $\O(1)$ operations on the $(a,b)$-trees
331 per operation on the ET-tree, plus $\O(1)$ other operations. We apply the standard theorems
332 on the complexity of $(a,b)$-trees \cite{clrs}.
335 \examplen{Connectivity acceleration}\id{accel}%
336 In most cases, the ET-trees are used with $a$~constant, but sometimes choosing~$a$ as a~function
337 of~$n$ can also have its beauty. Suppose that there is a~data structure which maintains an~arbitrary
338 spanning forest of a~dynamic graph. Suppose also that the structure works in time $\O(\log^k n)$
339 per operation and that it reports $\O(1)$ changes in the spanning forest for every change
340 in the graph. If we keep the spanning forest in ET-trees with $a=\log n$, the updates of the
341 data structure cost an~extra $\O(\log^2 n / \log\log n)$, but queries accelerate to $\O(\log
344 \paran{ET-trees with weights}
345 In some cases, we will also need to represent weighted graphs and enumerate the non-tree
346 edges in order of their increasing weights (in fact, it will be sufficient to find the
347 lightest one, remove it and iterate). This can be handled by a~minute modification of the
350 The tree edges will remember their weight in the corresponding internal keys of the ET-tree.
351 We replace each list of non-tree edges by an~$(a,b)$-tree keeping the edges sorted by weight.
352 We also store the minimum element of the tree separately, so that it can be accessed in constant
353 time. The boolean \em{marker} will then become the minimum weight of a~non-tree edge attached to the
354 particular subtree, which can be recalculated as easy as the markers can. Searching for the
355 lightest non-tree edge then just follows the modified markers.
357 The time complexities of all operations therefore remain the same, with a~possible
358 exception of the operations on non-tree edges, to which we have added the burden of
359 updating the new $(a,b)$-trees. This however consists of $\O(1)$ updates per a~single
360 call to \<InsertNontree> or \<DeleteNontree>, which takes $\O(a\log_a n)$ time only.
361 We can therefore conclude:
363 \corn{Weighted ET-trees}\id{wtet}%
364 The time bounds in Theorem \ref{etthm} hold for the weighted ET-trees, too.
367 %--------------------------------------------------------------------------------
369 \section{Dynamic connectivity}
371 The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
372 has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update
373 $\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
374 updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
375 were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
376 A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
377 The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
378 de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.
380 The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
381 which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
382 edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
383 Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
384 replacement among the non-tree edges.
386 To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
387 L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
388 of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
389 We will maintain the following \em{invariants:}
392 \def\iinv{{\bo I\the\itemcount~}}
394 \:$F$~is the maximum spanning forest of~$G$ with respect to the levels. In other words,
395 if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uw)}$.
396 \:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices.
397 This implies that all~$F_i$ for $i>L$ are empty.
401 At the beginning, the graph contains no edges, so both invariants are trivially
402 satistifed. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.
404 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
405 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
406 smaller one. We will try to find the replacement edge of the highest possible
407 level that connects them back. From I1, we know that such an~edge cannot belong to
408 level greater than~$\ell$, so we start looking for it at level~$\ell$. According
409 to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
410 at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can increase the levels
411 of all edges of~$T_1$ without violating either invariant.
413 We now start enumerating the non-tree edges incident with~$T_1$. For each such edge,
414 we test whether its other endpoint lies in~$T_2$. If it does, we have found the replacement
415 edge and we insert it to~$F_\ell$. Otherwise we move the edge one level up. (This will
416 be the gist of our amortization argument: We can charge most of the work on level
417 increases and we know that the level of each edge can reach at most~$L$.)
419 If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
420 lower level and so on. If there is no replacement edge on level~0, the tree~$T$
421 remains disconnected.
424 We will use a~single ET-tree with~$a$ set to~2 for each level. For the $i$-th level, the ET-tree
425 ${\cal E}_i$ will represent the forest~$F_i$ and the non-tree edges of
426 level~$i$ will be attached to its vertices.
428 \algn{Insertion of an~edge}
430 \algin An~edge $uv$ to insert.
432 \:Ask the ET-tree ${\cal E}_0$ if $u$ and~$v$ are in the same component. If they are:
433 \::Add $uv$ to the list of non-tree edges in ${\cal E}_0$ at both $u$ and~$v$.
435 \::Add $uv$ to~$F_0$.
438 \algn{Deletion of an~edge}
440 \algin An~edge $uv$ to delete.
441 \:$\ell \= \ell(uv)$.
442 \:If $uv$ is a~non-tree edge:
443 \::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$.
445 \::Remove $uv$ from~$F_\ell$.
446 \::Call $\<Replace>(uv,\ell)$.
449 \algn{$\<Replace>(uv,i)$ -- Search for an~replacement edge for~$uv$ at level~$i$}
451 \:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively.
452 \:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$.
453 \:Move all level~$i$ edges in~$T_1$ to level~$i+1$ and insert them to~${\cal E}_{i+1}$.
454 \:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
455 For each edge~$xy$, $x\in T_1$, do:
456 \::If $y\in T_2$, add the edge $xy$ to~$F_i$ and return.
457 \::Otherwise increase $\ell(xy)$ by one. This includes deleting~$xy$ from~${\cal E}_i$
458 and inserting it to~${\cal E}_{i+1}$.
459 \:If $i>0$, call $\<Replace>(xy,i-1)$.
462 \>Analysis of the time complexity is straightforward:
464 \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
465 Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized for both
466 \<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
470 The direct cost of an~\<Insert> is $\O(\log n)$ for the operations on the ET-trees
471 (by Theorem \ref{etthm}). We will have it pre-pay all level increases of the new
472 edge. Since the levels never decrease, each edge can be brought a~level up at most
473 $L=\lfloor\log n\rfloor$ times. Every increase costs $\O(\log n)$ on the ET-tree
474 operations, so we pay $\O(\log^2 n)$ for all of them.
476 A~\<Delete> costs $\O(\log^2 n)$ directly, as we might have to update all~$L$
477 ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization of
478 \<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
481 To bring the complexity of \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
482 we apply the trick from Example \ref{accel} and store~$F_0$ in a~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
483 This does not hurt the complexity of insertions and deletions, but allows for faster queries.
486 %--------------------------------------------------------------------------------
488 \section{Dynamic MSF}
490 Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
491 algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
492 have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
493 operation, or $\O(k\log^3 n)$ if only~$k$ different values of edge weights are allowed. They have solved
494 the decremental version of the problem first (which starts with a~given graph and only edge deletions
495 are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
496 We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
497 the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
498 in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
500 \paran{Decremental MSF}%
501 Turning the algorithm from the previous section to decremental MSF requires only two
502 changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
503 graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
504 MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
505 the lightest possible choice. We will therefore use the weighted version of the ET-trees (Corollary \ref{wtet})
506 and try the lightest non-tree edge incident with the examined tree first. We must ensure
507 that the lower levels cannot contain a~lighter replacement edge, but fortunately the
508 light edges tend to ``bubble up'' in the hierarchy of levels. This can be formalized as
509 the following invariant:
512 \def\iinv{{\bo I\the\itemcount~}}
515 \:On every cycle, the heaviest edge has the smallest level.
519 \>This easily implies that we select the right replacement edge:
522 Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
523 edges for~$e$, the lightest one is on the maximum level.
526 Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle
527 rule (\ref{cyclerule}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
528 In a~moment, we will show that the symmetric difference~$C$ of these two cycles is again a~cycle.
529 This implies that if $f_1$ is heavier than~$f_2$, then by I3 $f_1$~is the heaviest edge on~$C$, so
530 $\ell(f_1) \le \ell(f_2)$. Therefore the lightest of all replacement edges must have
534 Let $F^a$ and~$F^b$ be the trees of~$F-e$ in which the endpoints of~$e$ lie, and for
535 every edge~$g$ between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints.
536 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]$,
537 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
538 the edges $f_1$ and~$f_2$, which together form a~simple cycle.
541 We now have to make sure that the additional invariant is observed:
544 After every operation, I3 is satisfied.
547 When the structure is freshly initialized, I3 is obviously satisfied, because all edges
548 are at level~0. Sole deletions of edges (both tree and non-tree) cannot violate I3, so we need
549 to check only the replaces, in particular when an~edge~$e$ either gets its level increased
550 or becomes a~tree edge.
552 For the violation to happen, $e$~must be the heaviest on some cycle~$C$, so by the Cycle
553 rule, $e$~must be non-tree. The increase of $\ell(e)$ must therefore happen when~$e$ is
554 considered as a~replacement edge incident with some tree~$T_1$ at level $\ell=\ell(e)$.
555 We will pause the computation just before this increase and we will prove that
556 all other edges of~$C$ already are at levels greater than~$\ell$.
558 Let us first show that for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself
559 already are on the higher levels as they were moved there at the very beginning of the
560 search for the replacement edge. As the algorithm always tries the lightest candidate
561 for the replacement edge first, all non-tree edges incident with~$T_1$ which are lighter
562 than~$e$ were already considered and thus also moved one level up. This includes all
563 other edges of~$C$ that are incident with~$T_1$.
565 The case of edges that do not touch~$T_1$ is easy to handle: Such edges do not exist.
566 If they did, at least two edges of~$C$ would have to be non-tree edges connecting~$T_1$
567 with the other trees at level~$\ell$, so one of them that is lighter than~$e$ would be selected as the
568 replacement edge before~$e$ could be considered.
573 \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
574 When we start with a~graph with $n$~vertices and~$m\ge n$ edges and we perform
575 $d$~edge deletions, the MSF can be maintained in time $\O((m+d)\cdot\log^2 n)$.
577 \paran{Fully dynamic MSF}%
578 The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
579 reduction whose properties are summarized by the following theorem:
581 \thmn{MSF dynamization, Henzinger et al.~\cite{henzinger:twoec}, Holm et al.~\cite{holm:polylog}}
582 Suppose that we have a~decremental MSF algorithm that for any $a$,~$b$ can be initialized
583 on a~graph with~$a$ vertices and~$b$ edges and then it executes an~arbitrary sequence
584 of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
585 Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
586 with no edges, that performs $m$~insertions and deletions in amortized time:
588 \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.}
592 The reduction is very technical, but its essence is the following: We maintain a~logarithmic number
593 of decremental structures $A_0,\ldots,A_{\log n}$ of exponentially increasing sizes. Every non-tree
594 edge is contained in exactly one~$A_i$, tree edges can belong to multiple structures.
596 When an~edge is inserted, we union it with some of the $A_i$'s, build a~new decremental structure
597 and amortize the cost of the build over the insertions. Deletes of non-tree edges are trivial.
598 Delete of a~non-tree edge is performed on all $A_i$'s containing it and the replacement edge is
599 sought among the replacement edges found in these structures. The unused replacement edges then have
600 to be reinserted back to the structure.
602 The original reduction of Henzinger et al.~handles the reinserts by a~mechanism of batch insertions
603 supported by their decremental structure, which is not available in our case. Holm et al.~have
604 replaced it by a~system of auxiliary edges inserted at various places in the structure.
605 We refer to the article \cite{holm:polylog} for details.
608 \corn{Fully dynamic MSF}
609 There is a~fully dynamic MSF algorithm that works in amortized time $\O(\log^4 n)$
610 per operation for graphs on $n$~vertices.
613 Apply the reduction from the previous theorem to the decremental algorithm we have
614 developed. This results in an~algorithm of amortized complexity $\O(\log^4 m)$ where~$m$
615 is the number of operations performed. This could be more than $\O(\log^4 n)$ if
616 $m$~is very large, but we can rebuild the whole structure after $n^2$~operations,
617 which brings $\log m$ down to $\O(\log n)$. The $\O(n^2\log^4 n)$ cost of the
618 rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation.
622 The limitation of MSF structures based on the Holm's algorithm for connectivity
623 to edge deletions only seems to be unavoidable. The invariant I3 could be easily
624 broken for many cycles at once whenever a~very light non-tree edge is inserted.
625 We could try increasing the level of the newly inserted edge, but we would quite
626 possibly hit I1 before we skipped the levels of all the heavies edges on the
629 On the other hand, if we decided to drop I3, we would encounter different problems.
630 We have enough time to scan all non-tree edges incident to the current tree~$T_1$
631 --- we can charge it on the level increases of its tree edges and if we use the
632 degree reduction from Lemma \ref{degred}, there are at most two non-tree edges
633 per vertex. (The reduction can be used dynamically as it always translates a~single
634 change of the original graph to $\O(1)$ changes of the reduced graph.) The lightest
635 replacement edge however could also be located in the super-trees of~$T_1$ on the
636 lower levels, which are too large to scan and both I1 and I2 prevent us from
637 charging the time on increasing levels there.
639 An~interesting special case in which insertions are possible is when all non-tree
640 edges have the same weight. This leads to the following algorithm for dynamic MSF
641 on~graphs with a~small set of allowed edge weights.
643 \paran{Dynamic MSF with limited edge weights}%
644 Let us assume for a~while that our graph has edges of only two different weights (let us say
645 1~and~2). We will drop our rule that all edge weights are distinct for a~moment and we recall that
646 the basic structural properties of the MST's from Section \ref{mstbasics} still hold.
648 We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge
649 weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm to maintain
650 an~arbitrary spanning forest~$F_1$ of~$G_1$, which is obviously minimum. Then we add
651 another instance~$\C_2$ to maintain a~spanning forest~$F_2$ of the graph $G_2\cup F_1$
652 such that all edges of~$F_1$ are forced to be in~$F_2$. Obviously, $F_2$~is the
653 MSF of the whole graph~$G$ --- if any edge of~$F_1$ were not contained in~$\msf(G)$,
654 we could use the standard exchange argument to create an~even lighter spanning tree.\foot{This
655 is of course the Blue lemma in action, but we have to be careful as we did not have proven it
656 for graphs with multiple edges of the same weight.}
658 When a~weight~2 edge is inserted to~$G$, we insert it to~$\C_2$ and it either enters~$F_2$
659 or becomes a~non-tree edge. Similarly, deletion of a~weight~2 edge is a~pure deletion in~$\C_2$,
660 because such edges can be replaced only by other weight~2 edges.
662 Insertion of edges of weight~1 needs more attention: We insert the edge to~$\C_1$. If~$F_1$
663 stays unchanged, we are done. If the new edge enters~$F_1$, we use Sleator-Tarjan trees
664 kept for~$F_2$ to check if the new edge covers some tree edge of weight~2. If this is not
665 the case, we insert the new edge to~$\C_2$ and hence also to~$F_2$ and we are done.
666 Otherwise we exchange one of the covered weight~2 edges~$f$ for~$e$ in~$\C_2$. We note
667 that~$e$ can inherit the level of~$f$ and $f$~can become a~non-tree edge without
668 changing its level. This adjustment can be performed in time $\O(\log^2 n)$, including
669 paying for the future level increases of the new edge.
671 Deletion of weight~1 edges is once more straightforward. We delete the edge from~$\C_1$.
672 If it has no replacement, we delete it from~$\C_2$ as well. If it has a~replacement,
673 we delete the edge from~$\C_2$ and insert the replacement on its place as described
674 above. We observe than this pair of operations causes an~insertion, deletion or
675 a~replacement in~$\C_2$.
677 This way, we can handle every insertion and deletion in time $\O(\log^2 n)$ amortized.
678 This construction can be iterated in an~obvious way: if we have $k$~distinct edge weights,
679 we build $k$~connectivity structures $\C_1,\ldots,\C_k$. The structure~$\C_i$ contains edges of
680 weight~$i$ and the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy:
682 \thmn{MSF with limited edge weights}
683 There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
684 per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.
687 A~change in the graph~$G$ involving an~edge of weight~$w$ causes a~change in~$\C_w$,
688 which can propagate to~$\C_{w+1}$ and so on, possibly up to~$\C_k$. In each~$\C_i$,
689 we spend time $\O(\log^2 n)$ by updating the connectivity structure according to
690 Theorem \ref{dyncon}.