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 customarily called an~\df{incremental} or \df{semidynamic} graph algorithm.
-We mentioned the Disjoint Set Union data structure of Tarjan and van Leeuwen (Theorem \ref{dfu})
+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,
bound in the cell-probe model which is stronger than RAM with $\O(\log n)$-bit
words.
+\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 mechanism to keep the forest minimum. This will indeed turn out to be true, although we cannot
+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.
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 would return the MSF of the current
-graph is of course possible, but somewhat impractical as this operation has to
+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 so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
+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 Theorem on Minimality by order
-(\ref{mstthm}), because any $F'$-light would be also $F$-light, which is impossible as $F$~was
+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$
disconnected.
The idea of reporting differences in the MSF indeed works very well. We can summarize
-what we have shown in the following lemma and use it to define the dynamic MSF.
+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
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)$ --- Insert an~edge $uv$ to~$G$. Return its unique
+\:$\<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)$.
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 in our application.}
+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~$w$ closest to $\<Root>(v)$ such that the edge
- $(\<Parent>(w),w)$ is the heaviest of those on the path from the root to~$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,x)$ --- Connect the trees containing $u$ and~$v$ by an~edge $(u,v)$ of
- weight~$x$. Assumes that $v~$is a tree root and $u$~lies in a~different tree.
+\:$\<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.
\>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-tree, one of the occurrences of each vertex is defined as its \df{active occurrence} and
+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 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.
+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 the sequence from $vAwBwCv$ to $wBwCvAw$.
+\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$.
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)$
\<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 and returns its counter.
+\<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
We can therefore conclude:
\corn{Weighted ET-trees}\id{wtet}%
-The time bounds in Theorem \ref{etthm} hold for the weighted ET-trees, too.
+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 in Theorem
+\ref{etthm}.
%--------------------------------------------------------------------------------
}
At the beginning, the graph contains no edges, so both invariants are trivially
-satistifed. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.
+satisfied. Newly inserted edges can 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
\::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$.
\endalgo
-\algn{$\<Replace>(uv,i)$ -- Search for an~replacement edge for~$uv$ at level~$i$}
+\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$.
\: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. This includes deleting~$xy$ from~${\cal E}_i$
- and inserting it to~${\cal E}_{i+1}$.
+\::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.
\<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
increases.
-To bring the complexity of \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
+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 a~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
-An~$\Omega(\log n/\log\log n)$ lower bound for amortized complexity of the dynamic connectivity
+\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 indexing of arrays.) So far, it is not known how to extend this algorithm
+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 MSF}
+\section{Dynamic spanning forests}\id{dynmstsect}%
Let us turn our attention back to the dynamic MSF now.
Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
\proof
Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle
-rule (\ref{cyclerule}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
+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
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 two edges of~$C$ would have to connect~$T_1$ with the other trees of level~$\ell$,
-so one of them that is lighter than~$e$ would be selected as the replacement edge before~$e$ could be considered.
+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
-\FIXME{The previous paragraph is incomplete, it does not take tree edges into account.}
-
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.
+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, Henzinger et al.~\cite{henzinger:twoec}, Holm et al.~\cite{holm:polylog}}
+\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.
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.~handles these reinserts by a~mechanism of batch insertions
+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}
+\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.
\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 that
-the basic structural properties of the MST's from Section \ref{mstbasics} still hold.
+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 maintaining
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 real numbers (or integers), 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 decreases 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 now 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 \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
+is assigned 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 assign to them 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 $\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
+
+\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 difference, 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 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 cannot be reverted by any later exchanges.)
+\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 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 bounded 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 searching
+for the single minimum tree.
\endpart
projects / saga.git / blobdiff