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