\section{Dynamic graph algorithms}
-In many applications, we often need to solve a~certain graph problem for a~sequence
-of graphs that differ only a~little, so recomputing the solution from scratch for
-every graph would be a~waste of time. In such cases, we usually turn our attention
-to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure
-that remembers a~graph and offers operations that modify the structure of the graph
-(let's say by insertion and deletion of edges) and also operations that query the
-result of the problem for the current state of the graph.
-A~typical example of a~problem solved by such algorithms is dynamic maintenance of
-connected components:
+In many applications, we often need to solve a~certain graph problem for a~sequence of graphs that
+differ only a~little, so recomputing the solution for every graph from scratch would be a~waste of
+time. In such cases, we usually turn our attention to \df{dynamic graph algorithms.} A~dynamic
+algorithm is in fact a~data structure that remembers a~graph. It offers operations that modify the
+structure of the graph and also operations that query the result of the problem for the current
+state of the graph. A~typical example of a~problem of this kind is dynamic maintenance of connected
+components:
\problemn{Dynamic connectivity}
Maintain an~undirected graph under a~sequence of the following operations:
\itemize\ibull
-\:$\<Init>(n)$ --- create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$,\foot{%
+\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
The structure could support dynamic addition and removal of vertices, too,
-but this is easy to add and infrequently used, so we will rather define
-the structure with a~fixed set of vertices for clarity.}
-\:$\<Insert>(G,u,v)$ --- insert an~edge $uv$ to~$G$ and return its unique
-identifier (assuming that the edge did not exist yet),
-\:$\<Delete>(G,e)$ --- delete an~edge specified by its identifier from~$G$,
-\:$\<Connected>(G,u,v)$ --- test if $u$ and~$v$ are in the same connected component of~$G$.
+but this is easy to add and infrequently used, so we will rather keep the set
+of vertices fixed for clarity.}
+\:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
+identifier. This assumes that the edge did not exist yet.
+\:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
+\:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
\endlist
\para
We have already encountered a~special case of dynamic connectivity when implementing the
Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
any edges from the graph, which makes the problem substantially easier. This special
-case is sometimes called an~\df{incremental} or \df{semidynamic} graph algorithm.
-We mentioned the Union-Find data structure of Tarjan and van Leeuwen that is able
+case is customarily called an~\df{incremental} or \df{semidynamic} graph algorithm.
+We mentioned the Disjoint Set Union data structure of Tarjan (Theorem \ref{dfu})
+which can be used for that: Connected components are represented by equivalence classes.
+Queries on connectedness translate to \<Find>, edge insertions to \<Find>
+followed by \<Union> if the new edge joins two different components. This way,
+a~sequence of $m$~operations starting with an~empty graph on $n$~vertices is
+processed in time $\O(n+m\timesalpha(m,n))$ and this holds even for the Pointer
+Machine. Fredman and Saks \cite{fredman:cellprobe} have proven a~matching lower
+bound in the cell-probe model which is stronger than RAM with $\O(\log n)$-bit
+words.
-time $\O(n+m\timesalpha(m,n))$
+\paran{Dynamic MSF}%
+In this chapter, we will focus on the dynamic version of the minimum spanning forest.
+This problem seems to be intimately related to the dynamic connectivity. Indeed, all known
+algorithms for dynamic connectivity maintain some sort of a~spanning forest. For example, in the
+incremental algorithm we have just mentioned, this forest is formed by the edges that have
+triggered the \<Union>s. This suggests that a~dynamic MSF algorithm could be obtained by modifying
+the mechanics of the data structure to keep the forest minimum. This will really turn out to be true, although we cannot
+be sure that it will lead to the most efficient solution possible --- as of now, the known lower
+bounds are very far.
+Incremental MST will be easy to achieve even in the few pages of this section, but making it fully
+dynamic will require more effort, so we will review some of the required building blocks before
+going into that.
+
+We however have to answer one important question first: What should be the output of
+our MSF data structure? Adding an~operation that returns the MSF of the current
+graph would be of course possible, but somewhat impractical as this operation would have to
+spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
+be making the \<Insert> and \<Delete> operations report the list of modifications
+of the MSF implied by the change in the graph.
+
+Let us see what happens when we \<Insert> an~edge~$e$ to a~graph~$G$ with its minimum spanning
+forest~$F$, obtaining a~new graph~$G'$ with its MSF~$F'$. If $e$~connects two components of~$G$ (and
+therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the following cases happens:
+Either $e$~is $F$-heavy and thus the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
+and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
+
+Correctness of the former case follows immediately from the Minimality Theorem (\ref{mstthm}),
+because any $F'$-light would be also $F$-light, which is impossible as $F$~was
+minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
+on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
+(\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$
+of~$F$ that contains both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
+apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest in the cut~$\delta_G(T_1)$
+and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
+\looseness=1 %%HACK%%
+
+A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
+an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
+the new components (again the Blue lemma in action). If there is no such
+replacement edge, we have deleted a~bridge, so the MSF has to remain
+disconnected.
+
+The idea of reporting differences in the MSF indeed works very well. We can summarize
+what we have shown by the following lemma and use it to define the dynamic MSF.
+
+\lemma
+An~\<Insert> or \<Delete> of an~edge in~$G$ causes at most one edge addition, edge
+removal or edge exchange in $\msf(G)$.
+
+\problemn{Dynamic minimum spanning forest}
+Maintain an~undirected graph with distinct weights on edges (drawn from a~totally ordered set)
+and its minimum spanning forest under a~sequence of the following operations:
+\itemize\ibull
+\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
+\:$\<Insert>(G,u,v,w)$ --- Insert an~edge $uv$ of weight~$w$ to~$G$. Return its unique
+ identifier and the list of additions and deletions of edges in $\msf(G)$.
+\:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
+ Return the list of additions and deletions of edges in $\msf(G)$.
+\endlist
+
+\paran{Incremental MSF}%
+To obtain an~incremental MSF algorithm, we need to keep the forest in a~data structure that
+supports search for the heaviest edge on the path connecting a~given pair
+of vertices. This can be handled efficiently by the Link-Cut trees of Sleator and Tarjan:
+
+\thmn{Link-Cut Trees, Sleator and Tarjan \cite{sleator:trees}}\id{sletar}%
+There is a~data structure that represents a~forest of rooted trees on~$n$ vertices.
+Each edge of the forest has a~weight drawn from a~totally ordered set. The structure
+supports the following operations in time $\O(\log n)$ amortized:\foot{%
+The Link-Cut trees can offer a~plethora of other operations, but we do not mention them
+as they are not needed for our problem.}
+\itemize\ibull
+\:$\<Parent>(v)$ --- Return the parent of~$v$ in its tree or \<null> if $v$~is a~root.
+\:$\<Root>(v)$ --- Return the root of the tree containing~$v$.
+\:$\<Weight>(v)$ --- Return the weight of the edge $(\<Parent(v)>,v)$.
+\:$\<PathMax>(v)$ --- Return the vertex~$u$ closest to $\<Root>(v)$ such that the edge
+ $(\<Parent>(u),u)$ is the heaviest of those on the path from the root to~$v$.
+ If more edges have the maximum weight, break the tie arbitrarily.
+ If there is no such edge ($v$~is the root itself), return \<null>.
+\:$\<Link>(u,v,w)$ --- Connect the trees containing $u$ and~$v$ by an~edge $(u,v)$ of
+ weight~$w$. Assumes that $v~$is a tree root and $u$~lies in a~different tree.
+\:$\<Cut>(v)$ --- Split the tree containing the non-root vertex $v$ to two trees by
+ removing the edge $(\<Parent>(v),v)$. Returns the weight of this edge.
+\:$\<Evert>(v)$ --- Modify the orientations of edges to make~$v$ the root of its tree.
+\endlist
+
+%% \>Additionally, all edges on the path from~$v$ to $\<Root>(v)$ can be enumerated in
+%% time $\O(\ell + \log n)$, where $\ell$~is the length of that path. This operation
+%% (and also the path itself) is called $\<Path>(v)$.
+%%
+%% \>If the weights are real numbers (or in general an~arbitrary group), the $\O(\log n)$
+%% operations also include:
+%%
+%% \itemize\ibull
+%% \:$\<PathWeight>(v)$ --- Return the sum of the weights on $\<Path>(v)$.
+%% \:$\<PathUpdate>(v,x)$ --- Add~$x$ to the weights of all edges on $\<Path>(v)$.
+%% \endlist
+
+\proof
+See \cite{sleator:trees}.
+\qed
+
+Once we have this structure, we can turn our ideas on updating of the MSF to
+an~incremental algorithm:
+
+\algn{\<Insert> in an~incremental MSF}
+\algo
+\algin A~graph~$G$ with its MSF $F$ represented as a~Link-Cut forest, an~edge~$uv$
+with weight~$w$ to be inserted.
+\:$\<Evert>(u)$. \cmt{$u$~is now the root of its tree.}
+\:If $\<Root>(v) \ne u$: \cmt{$u$~and~$v$ lie in different trees.}
+\::$\<Link>(v,u,w)$. \cmt{Connect the trees.}
+\::Return ``$uv$ added''.
+\:Otherwise: \cmt{both are in the same tree}
+\::$y\=\<PathMax>(v)$.
+\::$x\=\<Parent>(y)$. \cmt{Edge~$xy$ is the heaviest on $F[uv]$.}
+\::If $\<Weight>(y) > w$: \cmt{We have to exchange~$xy$ with~$uv$.}
+\:::$\<Cut>(y)$, $\<Evert>(v)$, $\<Link>(u,v,w)$.
+\:::Return ``$uv$~added, $xy$~removed''.
+\::Otherwise return ``no changes''.
+\algout The list of changes in~$F$.
+\endalgo
+
+\thmn{Incremental MSF}
+When only edge insertions are allowed, the dynamic MSF can be maintained in time $\O(\log n)$
+amortized per operation.
+
+\proof
+Every \<Insert> performs $\O(1)$ operations on the Link-Cut forest, which take
+$\O(\log n)$ each by Theorem \ref{sletar}.
+\qed
+
+\rem
+We can easily extend the semidynamic MSF algorithm to allow an~operation commonly called
+\<Backtrack> --- removal of the most recently inserted edge. It is sufficient to keep the
+history of all MSF changes in a~stack and reverse the most recent change upon backtrack.
+
+What are the obstacles to making the structure fully dynamic?
+Deletion of edges that do not belong to the MSF is trivial (we do not
+need to change anything) and so is deletion of bridges (we just remove the bridge
+from the Link-Cut tree, knowing that there is no edge to replace it). The hard part
+is the search for replacement edges after an~edge belonging to the MSF is deleted.
+
+This very problem also has to be solved by algorithms for fully dynamic connectivity,
+we will take a~look at them first.
+
+%--------------------------------------------------------------------------------
+
+\section{Eulerian Tour trees}
+
+An~important stop on the road to fully dynamic algorithms has the name \df{Eulerian Tour trees} or
+simply \df{ET-trees}. It is a~representation of forests introduced by Henzinger and King
+\cite{henzinger:randdyn} in their randomized dynamic algorithms. It is similar to the Link-Cut
+trees, but it is much simpler and instead of path operations it offers efficient operations on
+subtrees. It is also possible to attach auxiliary data to vertices and edges of the original tree.
+
+\defn\id{eulseq}%
+Let~$T$ be a~rooted tree. We will call a~sequence of vertices of~$T$ its \df{Eulerian Tour sequence (ET-sequence)}
+if it lists the vertices visited by the depth-first traversal of~$T$.
+More precisely, it can be generated by the following procedure $\<ET>(v)$
+when it is invoked on the root of the tree:
+\algo
+\:Record~$v$ in the sequence.
+\:For each son~$w$ of~$v$:
+\::Call $\<ET>(w)$.
+\::Record~$w$.
+\endalgo
+\>A~single tree can have multiple ET-sequences, corresponding to different orders in which the
+sons can be enumerated in step~2.
+
+In every ET-sequence, one of the occurrences of each vertex is defined as its \df{active occurrence} and
+it will be used to store auxiliary data associated with that vertex.
+
+\obs
+An~ET-sequence contains a~vertex of degree~$d$ exactly $d$~times except for the root which
+occurs $d+1$ times. The whole sequence therefore contains $2n-1$ elements. It indeed describes the
+order of vertices on an~Eulerian tour in the tree with all edges doubled. Let us observe what happens
+to an~ET-sequence when we modify the tree. (See the picture.)
+
+When we \em{delete} an~edge $uv$ from the tree~$T$ (let $u$~be the parent of~$v$), the sequence
+$AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two sequences $AuC$ and $vBv$.
+If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence
+transforms from $AuvuC$ to $AuC$ and $v$~alone.
+
+\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes its ET-sequence from $vAwBwCv$ to $wBwCvAw$.
+If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
+the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
+
+\em{Joining} the roots of two trees by a~new edge makes their ET-sequences $vAv$ and~$wBw$
+combine to $vAvwBwv$. Again, we have to handle the cases when $v$ or~$w$ has degree~1 separately:
+$v$~and~$wBw$ combine to $vwBwv$, and $v$~with~$w$ makes $vwv$.
+
+\float{\valign{\vfil#\vfil\cr
+\hbox{\epsfbox{pic/ettree.eps}}\cr
+\noalign{\qquad\quad}
+ \halign{#\hfil\cr
+ $T_1: 0121034546474308980$,~~$T_2: aba$. \cr
+ $T_1-34: 01210308980, 4546474$. \cr
+ $T_1\hbox{~rooted at~3}: 3454647430898012103$. \cr
+ $T_1+0a+T_2$: $0121034546474308980aba0$. \cr
+ }\cr
+}}{Trees and their ET-sequences}
+
+If any of the occurrences that we have removed from the sequence was active, there is always
+a~new occurrence of the same vertex that can stand in its place and inherit the auxiliary data.
+
+\para
+The ET-trees will store the ET-sequences as $(a,b)$-trees with the parameter~$a$ set upon
+initialization of the structure and with $b=2a$. We know from the standard theorems of $(a,b)$-trees
+(see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$
+and that all basic operations including insertion, deletion, search, splitting and joining the trees
+run in time $\O(b\log_a n)$ in the worst case.
+\looseness=-1 %%HACK%%
+
+We will use the ET-trees to maintain a~spanning forest of the dynamic graph. The auxiliary data of
+each vertex will hold a~list of edges incident with the given vertex, that do not lie in the
+forest. Such edges are usually called the \df{non-tree edges.}
+
+\defn
+\df{Eulerian Tour trees (ET-trees)} are a~data structure that represents a~forest of trees and a~set of non-tree
+edges associated with the vertices of the forest. To avoid confusion, we will distinguish between
+\df{original} vertices and edges (of the given trees) and the vertices and edges of the
+data structure. The structure consists of:
+\itemize\ibull
+\:A~collection of $(a,b)$-trees of some fixed parameters $a$ and~$b$.
+ Each such tree corresponds to one of the original trees~$T$. Its
+ leaves (in the usual tree order) correspond to the elements
+ of an~ET-sequence for~$T$. Each two consecutive leaves $u$ and~$v$ are separated
+ by a~unique key stored in an~internal vertex of the $(a,b)$-tree. This key is used to represent
+ the original edge~$uv$. Each original edge is therefore kept in both its orientations.
+\:Mappings \<act>, \<edge> and \<twin>:
+ \itemize\icirc
+ \:$\<act>(v)$ maps each original vertex to the leaf containing its active occurrence;
+ \:$\<edge>(e)$ of an~original edge~$e$ is one of the internal keys representing~it;
+ \:$\<twin>(k)$ pairs an~internal key~$k$ with the other internal key of the same original edge.
+ \endlist
+\:A~list of non-tree edges placed in each leaf. The lists are allowed to be non-empty only
+ in the leaves that represent active occurrences of original vertices.
+\:Boolean \df{markers} in the internal vertices that signal presence of a~non-tree
+ edge anywhere in the subtree rooted at the internal vertex.
+\:Counters $\<leaves>(v)$ that contain the number of leaves in the subtree rooted at~$v$.
+\endlist
+
+\defn
+The ET-trees support the following operations on the original trees:
+\itemize\ibull
+\:\<Create> --- Create a~single-vertex tree.
+\:$\<Link>(u,v)$ --- Join two different trees by an~edge~$uv$ and return a~unique identifier
+ of this edge.
+\:$\<Cut>(e)$ --- Split a~tree by removing the edge~$e$ given by its identifier.
+\:$\<Connected>(u,v)$ --- Test if the vertices $u$ and~$v$ lie in the same tree.
+\:$\<Size>(v)$ --- Return the number of vertices in the tree containing the vertex~$v$.
+\:$\<InsertNontree>(v,e)$ --- Add a~non-tree edge~$e$ to the list at~$v$ and return a~unique
+ identifier of this edge.
+\:$\<DeleteNontree>(e)$ --- Delete a~non-tree edge~$e$ given by its identifier.
+\:$\<ScanNontree>(v)$ --- Return a~list of non-tree edges associated with the vertices
+ of the $v$'s tree.
+\endlist
+
+\impl
+We will implement the operations on the ET-trees by translating the intended changes of the
+ET-sequences to operations on the $(a,b)$-trees. The role of identifiers of the original vertices
+and edges will be of course played by pointers to the respective leaves and internal keys of
+the $(a,b)$-trees.
+
+\<Cut> of an~edge splits the $(a,b)$-tree at both internal keys representing the given edge
+and joins them back in the different order.
+
+\<Link> of two trees can be accomplished by making both vertices the roots of their trees first
+and joining the roots by an~edge afterwards. Re-rooting involves splits and joins of $(a,b)$-trees.
+As we can split at any occurrence of the new root vertex, we will use the active occurrence
+which we remember. Linking of the roots is translated to joining of the $(a,b)$-trees.
+
+\<Connected> follows parent pointers from both $u$ and~$v$ to the roots of their trees.
+Then it checks if the roots are equal.
+
+\<Size> finds the root~$r$ and returns $\<leaves>(r)$.
+
+\<InsertNontree> finds the leaf $\<act>(v)$ containing the list of $v$'s non-tree edges
+and inserts the new edge there. The returned identifier will consist from the pointer to
+the edge and the vertex in whose list it is stored. Then we have to recalculate the markers
+on the path from $\<act>(v)$ to the root. \<DeleteNontree> is analogous.
+
+Whenever any other operation changes a~vertex of the tree, it will also update its marker and
+counter and, if necessary, the markers and counters on the path to the root.
+
+\<ScanNontree> traverses the tree recursively from the root, but it does not enter the
+subtrees whose roots are not marked.
+
+Analysis of time complexity of the operations is now straightforward:
+
+\thmn{Eulerian Tour trees, Henzinger and Rauch \cite{henzinger:randdyn}}\id{etthm}%
+The ET-trees perform the operations \<Link> and \<Cut> in time $\O(a\log_a n)$, \<Create>
+in $\O(1)$, \<Connected>, \<Size>, \<InsertNontree>, and \<DeleteNontree> in $\O(\log_a n)$, and
+\<ScanNontree> in $\O(a\log_a n)$ per edge reported. Here $n$~is the number of vertices
+in the original forest and $a\ge 2$ is an~arbitrary constant.
+
+\proof
+We set $b=2a$. Our implementation performs $\O(1)$ operations on the $(a,b)$-trees
+per operation on the ET-tree, plus $\O(1)$ other work. We apply the standard theorems
+on the complexity of $(a,b)$-trees \cite{clrs}.
+\qed
+
+\examplen{Connectivity acceleration}\id{accel}%
+In most cases, the ET-trees are used with $a$~constant, but sometimes choosing~$a$ as a~function
+of~$n$ can also have its beauty. Suppose that there is a~data structure which maintains an~arbitrary
+spanning forest of a~dynamic graph. Suppose also that the structure works in time $\O(\log^k n)$
+per operation and that it reports $\O(1)$ changes in the spanning forest for every change
+in the graph. If we keep the spanning forest in ET-trees with $a=\log n$, the updates of the
+data structure cost an~additional $\O(\log^2 n / \log\log n)$, but connectivity queries accelerate to $\O(\log
+n/\log\log n)$.
+
+\paran{ET-trees with weights}
+In some cases, we will also need a~representation of weighted graphs and enumerate the non-tree
+edges in order of their increasing weights (in fact, it will be sufficient to find the
+lightest one, remove it and iterate). This can be handled by a~minute modification of the
+ET-trees.
+
+The tree edges will remember their weight in the corresponding internal keys of the ET-tree.
+We replace each list of non-tree edges by an~$(a,b)$-tree keeping the edges sorted by weight.
+We also store the minimum element of that tree separately, so that it can be accessed in constant
+time. The boolean \em{marker} will then become the minimum weight of a~non-tree edge attached to the
+particular subtree, which can be recalculated as easy as the markers can. Searching for the
+lightest non-tree edge then just follows the modified markers.
+
+The time complexities of all operations therefore remain the same, with a~possible
+exception of the operations on non-tree edges, to which we have added the burden of
+updating the new $(a,b)$-trees. This however consists of $\O(1)$ updates per a~single
+call to \<InsertNontree> or \<DeleteNontree>, which takes $\O(a\log_a n)$ time only.
+We can therefore conclude:
+
+\corn{Weighted ET-trees}\id{wtet}%
+In weighted ET-trees, the operations \<InsertNontree> and \<DeleteNontree> have time
+complexity $\O(a\log_a n)$. All other operations take the same time as indicated by Theorem
+\ref{etthm}.
%--------------------------------------------------------------------------------
-\section{Sleator-Tarjan trees}
+\section{Dynamic connectivity}
+
+The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
+has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and
+$\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
+updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
+were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
+A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
+The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
+de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.
+
+The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
+which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
+edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
+Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
+replacement among the non-tree edges.
+
+To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
+L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
+of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
+We will maintain the following \em{invariants:}
+
+{\narrower
+\def\iinv{{\bo I\the\itemcount~}}
+\numlist\iinv
+\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
+if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
+\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
+(This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
+anyway.)
+\endlist
+}
+
+At the beginning, the graph contains no edges, so both invariants are trivially
+satisfied. Newly inserted edges enter level~0, which cannot break I1 nor~I2.
+
+When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
+trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
+smaller one. We will try to find the replacement edge of the highest possible
+level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
+a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According
+to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
+at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can move all level~$\ell$
+edges of~$T_1$ to level~$\ell+1$ without violating either invariant.
+
+We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
+is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
+whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
+edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
+will be the grist for the mill of our amortization argument: We can charge most of the work on level
+increases and we know that the level of each edge can reach at most~$L$.)
+
+If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
+lower level and so on. If there is no replacement edge at level~0, the tree~$T$
+remains disconnected.
+
+\impl
+For each level~$\ell$, we will use a~separate ET-tree ${\cal E}_\ell$ with~$a$ set to~2,
+which will represent the forest~$F_\ell$ and the non-tree edges at that particular level.
+Besides operations on the non-tree edges, we also need to find the tree edges of level~$\ell$
+when we want to bring them one level up. This can be accomplished either by modifying the ET-trees
+to attach two lists of edges attached to vertices instead of one, or by using a~second ET-tree.
+
+\algn{Insertion of an~edge}
+\algo
+\algin An~edge $uv$ to insert.
+\:$\ell(uv) \= 0$.
+\:Ask the ET-tree ${\cal E}_0$ if $u$ and~$v$ are in the same component. If they are:
+\::Add $uv$ to the list of non-tree edges in ${\cal E}_0$ at both $u$ and~$v$.
+\:Otherwise:
+\::Add $uv$ to~$F_0$.
+\endalgo
+
+\algn{Deletion of an~edge}
+\algo
+\algin An~edge $uv$ to delete.
+\:$\ell \= \ell(uv)$.
+\:If $uv$ is a~non-tree edge:
+\::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$.
+\:Otherwise:
+\::Remove $uv$ from~$F_\ell$ and hence also from $F_0,\ldots,F_{\ell-1}$.
+\::Call $\<Replace>(uv,\ell)$ to get the replacement edge~$f$.
+\::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$.
+\endalgo
+
+\algn{$\<Replace>(uv,i)$ -- Search for replacement for edge~$uv$ at level~$i$}
+\algo
+\algin An~edge~$uv$ to replace and a~level~$i$ such that there is no replacement
+at levels greater than~$i$.
+\:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively.
+\:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$.
+\:Find all level~$i$ edges in~$T_1$ using ${\cal E}_i$ and move them to level~$i+1$.
+\:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
+ For each edge~$xy$, $x\in T_1$, do:
+\::If $y\in T_2$, remove~$xy$ from~${\cal E}_i$ and return it to the caller.
+\::Otherwise increase $\ell(xy)$ by one.
+ \hfil\break
+ This includes deleting~$xy$ from~${\cal E}_i$ and inserting it to~${\cal E}_{i+1}$.
+\:If $i>0$, call $\<Replace>(xy,i-1)$.
+\:Otherwise return \<null>.
+\algout The replacement edge.
+\endalgo
+
+\>As foretold, time complexity will be analysed by amortization on the levels.
+
+\thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
+Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per
+\<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
+in the worst case.
+
+\proof
+The direct cost of an~\<Insert> is $\O(\log n)$ for the operations on the ET-trees
+(by Theorem \ref{etthm}). We will also have the insertion pre-pay all level increases of the new
+edge. Since the levels never decrease, each edge can be brought a~level up at most
+$L=\lfloor\log n\rfloor$ times. Every increase costs $\O(\log n)$ on the ET-tree
+operations, so we pay $\O(\log^2 n)$ for all of them.
+
+A~\<Delete> costs $\O(\log^2 n)$ directly, as we might have to update all~$L$
+ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization of
+\<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
+increases.
+
+To bring the complexity of the operation \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
+we apply the trick from Example \ref{accel} and store~$F_0$ in an~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
+This does not hurt the complexity of insertions and deletions, but allows for faster queries.
+\qed
+
+\rem\id{dclower}%
+An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity
+problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell
+probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm
+\cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and
+$\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims
+that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations,
+so it does not fit the definition of the PM we use. The algorithm only does not
+need direct indexing of arrays.) So far, it is not known how to extend this algorithm
+to fit our needs, so we omit the details.
+
+%--------------------------------------------------------------------------------
+
+\section{Dynamic spanning forests}\id{dynmstsect}%
+
+Let us turn our attention back to the dynamic MSF.
+Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
+algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
+have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
+operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved
+the decremental version of the problem first (which starts with a~given graph and only edge deletions
+are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
+We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
+the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
+in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
+
+\paran{Decremental MSF}%
+Turning the algorithm from the previous section to the decremental MSF requires only two
+changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
+graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
+MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
+the lightest possible choice. We will therefore use the weighted version of the ET-trees (Corollary \ref{wtet})
+and scan the lightest non-tree edge incident with the examined tree first. We must ensure
+that the lower levels cannot contain a~lighter replacement edge, but fortunately the
+light edges tend to ``bubble up'' in the hierarchy of levels. This can be formalized
+in form of the following invariant:
+
+{\narrower
+\def\iinv{{\bo I\the\itemcount~}}
+\numlist\iinv
+\itemcount=2
+\:On every cycle, the heaviest edge has the smallest level.
+\endlist
+}
+
+\>This immediately implies that we always select the right replacement edge:
+
+\lemma\id{msfrepl}%
+Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
+edges for~$e$, the lightest one is at the maximum level.
+
+\proof
+Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle
+rule (Lemma \ref{redlemma}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
+In a~moment, we will show that the symmetric difference~$C$ of these two cycles is again a~cycle.
+This implies that if $f_1$ is heavier than~$f_2$, then $f_1$~is the heaviest edge on~$C$, so
+$\ell(f_1) \le \ell(f_2)$ by I3. Therefore the lightest of all replacement edges must have
+the maximum level.
+
+Why is~$C$ a~cycle:
+Let $F^a$ and~$F^b$ be the trees of~$F-e$ in which the endpoints of~$e$ lie, and for
+every edge~$g$ going between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints.
+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]$,
+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
+the edges $f_1$ and~$f_2$, which together form a~simple cycle.
+\qed
+
+We now have to make sure that the additional invariant is really observed:
+
+\lemma\id{ithree}%
+After every operation, the invariant I3 is satisfied.
+
+\proof
+When the structure is freshly initialized, I3 is obviously satisfied, as all edges
+are at level~0. Sole deletions of edges (both tree and non-tree) cannot violate I3, so we need
+to check only the replaces, in particular the place when an~edge~$e$ gets its level increased.
+
+For the violation to happen for the first time, $e$~must be the heaviest on
+some cycle~$C$, so by the Cycle rule, $e$~must be non-tree. The increase of
+$\ell(e)$ must therefore take place when~$e$ is considered as a~replacement
+edge incident with some tree~$T_1$ at level $\ell=\ell(e)$. We will pause the
+computation just before this increase and we will prove that all other edges
+of~$C$ already are at levels greater than~$\ell$, so the violation cannot occur.
+
+Let us first show that for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself
+already are at the higher levels as they were moved there at the very beginning of the
+search for the replacement edge. The other tree edges incident with~$T_1$ would have
+lower levels, which is impossible since the invariant would be already violated.
+Non-tree edges of~$C$ incident with~$T_1$ are lighter than~$e$, so they were already considered
+as~candidates for the replacement edge, because the algorithm always picks the lightest
+candidate first. Such edges therefore have been already moved a~level up.
+
+The case of edges of~$C$ that do not touch~$T_1$ is easy to handle: Such edges do not exist.
+If they did, at least one more edge of~$C$ besides~$e$ would have to connect~$T_1$ with the other
+trees of level~$\ell$. We already know that this could not be a~tree edge. If it were a~non-tree
+edge, it could not have level greater than~$\ell$ by~I1 nor smaller than~$\ell$ by~I3. Therefore
+it would be a~level~$\ell$ edge lighter than~$e$, and as such it would have been selected as the
+replacement edge before $e$~was.
+\qed
+
+We can conclude:
+
+\thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
+When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of
+edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then
+updated in time $\O(\log^2 n)$ amortized per operation.
+
+\paran{Fully dynamic MSF}%
+The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
+reduction whose properties are summarized in the following theorem:
+
+\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
+Suppose that we have a~decremental MSF algorithm with the following properties:
+\numlist\ndotted
+\:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
+\:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
+\endlist
+\>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
+with no edges, that performs $m$~insertions and deletions in amortized time:
+$$
+\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.}
+$$
+
+\proofsketch
+The reduction is very technical, but its essence is the following: We maintain a~logarithmic number
+of decremental structures $A_0,\ldots,A_{\lfloor\log n\rfloor}$ of exponentially increasing sizes. Every non-tree
+edge is contained in exactly one~$A_i$, tree edges can belong to multiple structures.
+
+When an~edge is inserted, we union it with some of the $A_i$'s, build a~new decremental structure
+and amortize the cost of the build over the insertions. Deletes of non-tree edges are trivial.
+Delete of a~tree edge is performed on all $A_i$'s containing it and the replacement edge is
+sought among the replacement edges found in these structures. The unused replacement edges then have
+to be reinserted back to the structure.
+
+The original reduction of Henzinger et al.~\cite{henzinger:twoec} handles these reinserts by a~mechanism of batch insertions
+supported by their decremental structure, which is not available in our case. Holm et al.~have
+replaced it by a~system of auxiliary edges inserted at various places in the structure.
+We refer to the article \cite{holm:polylog} for details.
+\qed
+
+\corn{Fully dynamic MSF}\id{dynmsfcorr}%
+There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized
+per operation for graphs on $n$~vertices.
+
+\proof
+Apply the reduction from the previous theorem to the decremental algorithm we have
+developed. This results in an~algorithm of amortized complexity $\O(\log^4\max(m,n))$ where~$m$
+is the number of operations performed. This could exceed $\O(\log^4 n)$ if
+$m$~is very large, but we can rebuild the whole structure after $n^2$~operations,
+which brings $\log m$ down to $\O(\log n)$. The $\O(n^2\log^4 n)$ cost of the
+rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation.
+\qed
+
+\rem
+The limitation of MSF structures based on the Holm's algorithm for connectivity
+to only edge deletions seems to be unavoidable. The invariant I3 could be easily
+broken for many cycles at once whenever a~very light non-tree edge is inserted.
+We could try increasing the level of the newly inserted edge, but we would quite
+likely hit I1 before we managed to skip the levels of all the heaviest edges on the
+particular cycles.
+
+On the other hand, if we decided to drop I3, we would encounter different obstacles. The ET-trees can
+bring the lightest non-tree incident with the current tree~$T_1$, but the lightest replacement edge
+could also be located in the super-trees of~$T_1$ at the lower levels, which are too large to scan
+and both I1 and I2 prevent us from charging the time on increasing levels there.
+
+An~interesting special case in which insertions are possible is when all non-tree
+edges have the same weight. This leads to the following algorithm for dynamic MSF
+on~graphs with a~small set of allowed edge weights. It is based on an~idea similar
+to the $\O(k\log^3 n)$ algorithm of Henzinger and King \cite{henzinger:randdyn},
+but have adapted it to use the better results on dynamic connectivity we have at hand.
+
+\paran{Dynamic MSF with limited edge weights}%
+Let us assume for a~while that our graph has edges of only two different weights (let us say
+1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall
+the observation in \ref{multiweight} that the basic structural properties of
+the MST's from Section \ref{mstbasics} still hold.
+
+We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge
+weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm to maintain
+an~arbitrary spanning forest~$F_1$ of~$G_1$, which is obviously minimum. Then we add
+another instance~$\C_2$ to maintain a~spanning forest~$F_2$ of the graph $G_2\cup F_1$
+such that all edges of~$F_1$ are forced to be in~$F_2$. Obviously, $F_2$~is the
+MSF of the whole graph~$G$ --- if any edge of~$F_1$ were not contained in~$\msf(G)$,
+we could use the standard exchange argument to create an~even lighter spanning tree.
+
+When a~weight~2 edge is inserted to~$G$, we insert it to~$\C_2$ and it either enters~$F_2$
+or becomes a~non-tree edge. Similarly, deletion of a~weight~2 edge is a~pure deletion in~$\C_2$,
+because such edges can be replaced only by other weight~2 edges.
+
+Insertion of edges of weight~1 needs more attention: We insert the edge to~$\C_1$. If~$F_1$
+stays unchanged, we are done. If the new edge enters~$F_1$, we use a~Sleator-Tarjan tree
+kept for~$F_2$ to check if the new edge covers some tree edge of weight~2. If this is not
+the case, we insert the new edge to~$\C_2$ and hence also to~$F_2$ and we are done.
+Otherwise we exchange one of the covered weight~2 edges~$f$ for~$e$ in~$\C_2$. We note
+that~$e$ can inherit the level of~$f$ and $f$~can become a~non-tree edge without
+changing its level. This adjustment can be performed in time $\O(\log^2 n)$, including
+paying for the future level increases of the new edge.
+
+Deletion of weight~1 edges is once more straightforward. We delete the edge from~$\C_1$.
+If it has no replacement, we delete it from~$\C_2$ as well. If it has a~replacement,
+we delete the edge from~$\C_2$ and insert the replacement on its place as described
+above. We observe than this pair of operations causes an~insertion, deletion or
+a~replacement in~$\C_2$.
+
+This way, we can handle every insertion and deletion in time $\O(\log^2 n)$ amortized.
+This construction can be iterated in an~obvious way: if we have $k$~distinct edge weights,
+we build $k$~connectivity structures $\C_1,\ldots,\C_k$. The structure~$\C_i$ contains edges of
+weight~$i$ together with the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy:
+
+\thmn{MSF with limited edge weights}
+There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
+per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.
+
+\proof
+A~change in the graph~$G$ involving an~edge of weight~$w$ causes a~change in~$\C_w$,
+which can propagate to~$\C_{w+1}$ and so on, possibly up to~$\C_k$. In each~$\C_i$,
+we spend time $\O(\log^2 n)$ by updating the connectivity structure according to
+Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan trees
+by Theorem \ref{sletar}.
+\qed
+
+%--------------------------------------------------------------------------------
+
+\section{Almost minimum trees}\id{kbestsect}%
+
+In some situations, finding the single minimum spanning tree is not enough and we are interested
+in the $K$~lightest spanning trees, usually for some small value of~$K$. Katoh, Ibaraki
+and Mine \cite{katoh:kmin} have given an~algorithm of time complexity $\O(m\log\beta(m,n) + Km)$,
+building on the MST algorithm of Gabow et al.~\cite{gabow:mst}.
+Subsequently, Eppstein \cite{eppstein:ksmallest} has discovered an~elegant preprocessing step which allows to reduce
+the running time to $\O(m\log\beta(m,n) + \min(K^2,Km))$ by eliminating edges
+which are either present in all $K$ trees or in none of them.
+We will show a~variant of their algorithm based on the MST verification
+procedure of Section~\ref{verifysect}.
+
+In this section, we will require the edge weights to be numeric, because
+comparisons are certainly not sufficient to determine the second best spanning tree. We will
+assume that our computation model is able to add, subtract and compare the edge weights
+in constant time.
+
+Let us focus on finding the second lightest spanning tree first.
+
+\paran{Second lightest spanning tree}%
+Suppose that we have a~weighted graph~$G$ and a~sequence $T_1,\ldots,T_z$ of all its spanning
+trees. Also suppose that the weights of these spanning trees are distinct and that the sequence
+is ordered by weight, i.e., $w(T_1) < \ldots < w(T_z)$ and $T_1 = \mst(G)$. Let us observe
+that each tree is similar to at least one of its predecessors:
+
+\lemman{Difference lemma}\id{kbl}%
+For each $i>1$ there exists $j<i$ such that $T_i$ and~$T_j$ differ by a~single edge exchange.
+
+\proof
+We know from the Monotone exchange lemma (\ref{monoxchg}) that $T_1$ can be transformed
+to~$T_i$ by a~sequence of edge exchanges which never decrease tree weight. The last
+exchange in this sequence therefore obtains~$T_i$ from a~tree of the desired properties.
+\qed
+
+\para
+This lemma implies that the second best spanning tree~$T_2$ differs from~$T_1$ by a~single
+edge exchange. It remains to find which exchange it is. Let us consider the exchange
+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$
+of weight $w(T_1)-w(e)+w(f)$. To obtain~$T_2$, we have to find~$e$ and~$f$ such that the
+difference $w(f)-w(e)$ is the minimum possible. Thus for every~$f$, the edge~$e$~must be always
+the heaviest on the path $T_1[f]$. We can apply the algorithm from Corollary \ref{rampeaks}
+and find the heaviest edges (peaks) of all such paths and thus examine all possible choices of~$f$
+in linear time. So we get:
+
+\lemma
+For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find
+edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum.
+
+\nota
+We will call this procedure \df{finding the best exchange in $(H,T)$.}
+
+\cor
+Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
+
+\paran{Third lightest spanning tree}%
+Once we know~$T_1$ and~$T_2$, how to get~$T_3$? According to the Difference lemma, $T_3$~can be
+obtained by a~single exchange from either~$T_1$ or~$T_2$. Therefore we need to find the
+best exchange for~$T_2$ and the second best exchange for~$T_1$ and use the better of them.
+The latter is not easy to find directly, so we will make a~minor side step.
+
+We know that $T_2$ equals $T_1-e+f$ for some edges $e$ and~$f$. We define two auxiliary graphs:
+$G_1 := G/e$ and $G_2 := G-e$. The tree~$T_1/e$ is obviously the MST of~$G_1$
+(by the Contraction lemma) and $T_2$ is the MST of~$G_2$ (all $T_2$-light edges
+in~$G_2$ would be $T_1$-light in~$G$).
+
+\obs\id{tbobs}%
+The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
+
+\itemize\ibull
+\:If $T_3 = T_1-e'+f'$ for $e'\ne e$, then $T_3/e = (T_1/e)-e'+f'$ in~$G_1$.
+\:If $T_3 = T_1-e+f'$, then $T_3 = T_2 - f + f'$ in~$G_2$.
+\:If $T_3 = T_2-e'+f'$, then this exchange is found in~$G_2$.
+\endlist
+
+\>Conversely, a~single exchange in $(G_1,T_1/e)$ or in $(G_2,T_2)$ corresponds
+to an~exchange in either~$(G,T_1)$ or $(G,T_2)$.
+Even stronger, a~spanning tree~$T$ of~$G$ either contains~$e$ and then $T\sgc
+e$ is a~spanning tree of~$G_1$, or $T$~doesn't contain~$e$ and so it is
+a~spanning tree of~$G_2$.
+
+Thus we can run the previous algorithm for finding the best edge exchange
+on both~$G_1$ and~$G_2$ and find~$T_3$ again in time $\O(m)$.
+
+\paran{Further spanning trees}%
+The construction of auxiliary graphs can be iterated to obtain $T_1,\ldots,T_K$
+for an~arbitrary~$K$. We will build a~\df{meta-tree} of auxiliary graphs. Each node of this meta-tree
+carries a~graph\foot{This graph is always derived from~$G$ by a~sequence of edge deletions
+and contractions. It is tempting to say that it is a~minor of~$G$, but this is not true as we
+preserve multiple edges.} and its minimum spanning tree. The root node contains~$(G,T_1)$,
+its sons have $(G_1,T_1/e)$ and $(G_2,T_2)$. When $T_3$ is obtained by an~exchange
+in one of these sons, we attach two new leaves to that son and we let them carry the two auxiliary
+graphs derived by contracting or deleting the exchanged edge. Then we find the best
+edge exchanges among all leaves of the new meta-tree and repeat the process. By Observation \ref{tbobs},
+each spanning tree of~$G$ is generated exactly once. The Difference lemma guarantees that
+the trees are enumerated in the increasing order.
+
+Recalculating the best exchanges in all leaves of the meta-tree after generating each~$T_i$
+is of course not necessary, because most leaves stay unchanged. We will rather remember
+the best exchange for each leaf and keep the weight differences of these exchanges in a~heap. In every step, we will
+delete the minimum from the heap and use the exchange in the particular leaf to generate
+a~new spanning tree. Then we will create the new leaves, calculate their best exchanges and insert
+them into the heap. The algorithm is now straightforward and so will be its analysis:
+
+\algn{Finding $K$ best spanning trees}\id{kbestalg}%
+\algo
+\algin A~weighted graph~$G$, its MST~$T_1$ and an~integer $K>0$.
+\:$R\=$ a~meta tree whose vertices carry triples $(G',T',F')$. Initially
+ it contains just a~root with $(G,T_1,\emptyset)$.
+ \hfil\break
+ \cmt{$G'$ is a~graph, $T'$~is its MST, and~$F'$ is a~set of edges of~$G$
+ that are contracted in~$G'$.}
+\:$H\=$ a~heap of quadruples $(\delta,r,e,f)$ ordered on~$\delta$, initially empty.
+ \hfil\break
+ \cmt{Each quadruple describes an~exchange of~$e$ for~$f$ in a~leaf~$r$ of~$R$ and $\delta=w(f)-w(e)$
+ is the weight gain of this exchange.}
+\:Find the best edge exchange in~$(G,T_1)$ and insert it to~$H$.
+\:$i\= 1$.
+\:While $i<K$:
+\::Delete the minimum quadruple $(\delta,r,e,f)$ from~$H$.
+\::$(G',T',F') \=$ the triple carried by the leaf~$r$.
+\::$i\=i+1$.
+\::$T_i\=(T'-e+f) \cup F'$. \cmt{The next spanning tree}
+\::$r_1\=$ a~new leaf carrying $(G'/e,T'/e,F'+e)$.
+\::$r_2\=$ a~new leaf carrying $(G'-e,T_i,F')$.
+\::Attach~$r_1$ and~$r_2$ as sons of~$r$.
+\::Find the best edge exchanges in~$r_1$ and~$r_2$ and insert them to~$H$.
+\algout The spanning trees $T_2,\ldots,T_K$.
+\endalgo
+
+\lemma\id{kbestl}%
+Given~$G$ and~$T_1$, we can find $T_2,\ldots,T_K$ in time $\O(Km + K\log K)$.
+
+\proof
+Generating each~$T_i$ requires finding the best exchange for two graphs and also $\O(1)$
+operations on the heap. The former takes $\O(m)$ according to Corollary \ref{rampeaks},
+and each heap operation takes $\O(\log K)$.
+\qed
+
+\rem
+The meta-tree is not needed for the actual operation of the algorithm --- it suffices
+to keep its leaves in the heap.
+
+\paran{Arbitrary weights}%
+While the assumption that the weights of all spanning trees are distinct has helped us
+in thinking about the problem, we should not forget that it is somewhat unrealistic.
+We could refine the proof of our algorithm and demonstrate that the algorithm indeed works
+without this assumption, but we will rather show that the ties can be broken easily.
+
+Let~$\delta$ be the minimum positive difference among the weights of all spanning trees
+of~$G$ and $e_1,\ldots,e_m$ be the edges of~$G$. We observe that it suffices to
+increase $w(e_i)$ by~$\delta_i = \delta/2^{i+1}$. The cost of every spanning tree
+has increased by at most $\sum_i\delta_i < \delta/2$, so if $T$~was lighter
+than~$T'$, it still is. On the other hand, no two trees share the same
+weight adjustment, so all tree weights are now distinct.
+
+The exact value of~$\delta$ is not easy to calculate, but closer inspection of the algorithm
+reveals that it is not needed at all. The only place where the edge weights are examined
+is when we search for the best exchange. In this case, we compare the differences of
+pairs of edge weights with each other. Each such difference is therefore adjusted
+by $\delta\cdot(2^{-i}-2^{-j})$ for some $i,j>1$, which again does not influence comparison
+of originally distinct differences. If two differences were identical, it is sufficient
+to look at their values of~$i$ and~$j$, i.e., at the identifiers of the edges.
+
+\paran{Invariant edges}%
+Our algorithm can be further improved for small values of~$K$ (which seems to be the common
+case in most applications) by the reduction of Eppstein \cite{eppstein:ksmallest}.
+We will observe that there are many edges of~$T_1$
+which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
+many edges of $G\setminus T_1$ which are excluded from all those spanning trees.
+The idea is the following (again assuming that the tree weights are distinct):
+
+\defn
+For an~edge $e\in T_1$, we define its \df{gain} $g(e)$ as the minimum weight gained by exchanging~$e$
+for another edge. Similarly, we define the gain $G(f)$ for $f\not\in T_1$. Put formally:
+$$\eqalign{
+g(e) &:= \min\{ w(f)-w(e) \mid f\in E, e\in T[f] \}, \cr
+G(f) &:= \min\{ w(f)-w(e) \mid e\in T[f] \}.\cr
+}$$
+
+\lemma\id{gaina}%
+When $t_1,\ldots,t_{n-1}$ are the edges of~$T_1$ in order of increasing gain,
+the edges $t_K,\ldots,t_{n-1}$ are present in all trees $T_2,\ldots,T_K$.
+
+\proof
+The best exchanges in~$T_1$ involving $t_1,\ldots,t_{K-1}$ produce~$K-1$ spanning trees
+of increasing weights. Any exchange involving $t_K,\ldots,t_n$ produces a~tree
+which is heavier or equal than all those trees. (We are ascertained by the Monotone exchange lemma
+that the gain of such exchanges need not be reverted later.)
+\qed
+
+\lemma\id{gainb}%
+When $q_1,\ldots,q_{m-n+1}$ are the edges of $G\setminus T_1$ in order of increasing gain,
+the edges $q_K,\ldots,q_{m-n+1}$ are not present in any of $T_2,\ldots,T_K$.
+
+\proof
+Similar to the previous lemma.
+\qed
+
+\para
+It is therefore sufficient to find $T_2,\ldots,T_K$ in the graph obtained from~$G$ by
+contracting the edges $t_K,\ldots,t_n$ and deleting $q_K,\ldots,q_{m-n+1}$. This graph
+has only $\O(K)$ vertices and $\O(K)$ edges. The only remaining hurdle is how to
+calculate the gains. For edges outside~$T_1$, it again suffices to find the peaks of the
+covered paths. The gains of MST edges require a~different algorithm, but Tarjan \cite{tarjan:applpc}
+has shown how to obtain them in time $\O(m\timesalpha(m,n))$.
+
+When we put the results of this section together, we can conclude:
+
+\thmn{Finding $K$ lightest spanning trees}\id{kbestthm}%
+For a~given graph~$G$ with real edge weights and a~positive integer~$K$, the $K$~best spanning trees can be found
+in time $\O(m\timesalpha(m,n) + \min(K^2,Km + K\log K))$.
+
+\proof
+First we find the MST of~$G$ in time $\O(m\timesalpha(m,n))$ using the Pettie's Optimal
+MST algorithm (Theorem \ref{optthm}). Then we calculate the gains of MST edges by the
+Tarjan's algorithm from \cite{tarjan:applpc}, again in $\O(m\timesalpha(m,n))$, and
+the gains of the other edges using our MST verification algorithm (Corollary \ref{rampeaks})
+in $\O(m)$. We use Lemma \ref{gaina} to identify edges that are required, and Lemma \ref{gainb}
+to find edges that are superfluous. We contract the former edges, remove the latter ones
+and run Algorithm \ref{kbestalg} to find the spanning trees. By Lemma \ref{kbestl}, it runs in
+the desired time.
+
+If~$K\ge m$, this reduction does not pay off, so we run Algorithm \ref{kbestalg}
+directly on the input graph.
+\qed
+
+\paran{Improvements}%
+It is an~interesting open question whether the algorithms of Section \ref{verifysect} can
+be modified to calculate all gains in linear time. The main procedure could be, but it requires having
+the input reduced to a~balance tree beforehand and here the Bor\o{u}vka trees fail. The Buchsbaum's
+Pointer-Machine algorithm (\ref{pmverify}) seems to be more promising.
+
+\paran{Large~$K$}%
+When $K$~is large, re-running the verification algorithm for every change of the graph
+is too costly. Frederickson \cite{frederickson:ambivalent} has shown how to find the best
+swaps dynamically, reducing the overall time complexity of Algorithm \ref{kbestalg}
+to $\O(Km^{1/2})$ and improving the bound in Theorem \ref{kbestthm} to $\O(m\timesalpha(m,n)
++ \min( K^{3/2}, Km^{1/2} ))$. It is open if the dynamic data structures of this
+chapter could be modified to bring the complexity of finding the next tree down
+to polylogarithmic.
+
+\paran{Multiple minimum trees}%
+Another nice application of Theorem \ref{kbestthm} is finding all minimum spanning
+trees in a~graph that does not have distinct edge weights. We find a~single MST using
+any of the algorithms of the previous chapters and then we use the enumeration algorithm
+of this section to find further spanning trees as long as their weights are equal to the minimum.
+
+We can even use the reduction of the number of edges from Lemmata \ref{gaina} and \ref{gainb}:
+we start with some fixed~$K$ and when we exhaust all~$K$ trees, we double~$K$ and restart
+the whole process. The extra time spent on these restarts is dominated by the time of the
+final pass.
+This finally settles the question that we have asked ourselves in Section \ref{mstbasics},
+namely whether we lose anything by assuming that all weights are distinct and by searching
+for just the single minimum tree.
\endpart
projects / saga.git / blobdiff