From 350058f530e1903f8d93ea2e00bec511f4c50ced Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 23 Apr 2008 21:07:12 +0200
Subject: [PATCH] First parts of the section on Almost minimum trees.

---
 PLAN       |  1 +
 adv.tex    |  8 +++++++-
 biblio.bib | 13 ++++++++++++-
 dyn.tex    | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 73 insertions(+), 2 deletions(-)

diff --git a/PLAN b/PLAN
index 8494170..0632004 100644
--- a/PLAN
+++ b/PLAN
@@ -35,6 +35,7 @@
   o  ET-trees
   o  Fully dynamic connectivity
   o  Dynamic MST
+  .  Almost minimum trees
 
 *  Ranking Combinatorial Objects
 
diff --git a/adv.tex b/adv.tex
index a573d97..047834b 100644
--- a/adv.tex
+++ b/adv.tex
@@ -1020,7 +1020,7 @@ sub-word of~$M_e$ in the intended interval).
 \>We are now ready to combine these steps and get the following theorem:
 
 \thmn{Verification of MST on the RAM}\id{ramverify}%
-There is a~RAM algorithm, which for every weighted graph~$G$ and its spanning tree~$T$
+There is a~RAM algorithm which for every weighted graph~$G$ and its spanning tree~$T$
 determines whether~$T$ is minimum and finds all $T$-light edges in~$G$ in time $\O(m)$.
 
 \proof
@@ -1032,6 +1032,12 @@ as there are $\O(1)$ query paths per edge, the first sum is $\O(\#\hbox{comparis
 which is $\O(m)$ by Theorem \ref{verify}.
 \qed
 
+\>In Section \ref{kbestsect}, we will need a~more specialized statement:
+
+\cor\id{rampeaks}%
+There is a~RAM algorithm which for every weighted tree~$T$ and a~set~$P$ of
+paths in~$T$ calculates the peaks of these paths in time $\O(n(T) + \vert P\vert)$.
+
 \paran{Verification on the Pointer Machine}\id{pmverify}%
 Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown that linear-time
 verification can be achieved even on the Pointer Machine. They first solve the
diff --git a/biblio.bib b/biblio.bib
index 3311556..f489749 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -6,7 +6,18 @@
     year = "2000",
     url = "citeseer.ist.psu.edu/bender00lca.html" }
 
-@inproceedings{ frederickson91ambivalent,
+@article{ frederickson:ambivalent,
+  author = "Frederickson, Greg N.",
+  title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
+  journal={SIAM journal on computing},
+  volume={26},
+  number={2},
+  pages={484--538},
+  year={1997},
+  publisher={Society for Industrial and Applied Mathematics}
+}
+
+@inproceedings{ frederickson:ambifocs,
     author = "Greg N. Frederickson",
     title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
diff --git a/dyn.tex b/dyn.tex
index a914c80..7274616 100644
--- a/dyn.tex
+++ b/dyn.tex
@@ -727,5 +727,58 @@ Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan tree
 by Theorem \ref{sletar}.
 \qed
 
+%--------------------------------------------------------------------------------
+
+\section{Almost minimum trees}\id{kbestsect}%
+
+In some situations, finding the 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~simplified 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 enough 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 best spanning tree, to begin with.
+
+\paran{Second best 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:
+
+\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 and 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 use the algorithm from Corollary \ref{rampeaks}
+to find the heaviest edges (peaks) of all such paths and examine all possible choices of~$f$
+in linear time. This implies the following:
+
+\lemma
+Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
+
+\paran{Getting further spanning trees}%
+When we know~$T_1$ and~$T_2$, how to get~$T_3$? According to Lemma \ref{kbl}, it 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.
+
 
 \endpart
-- 
2.39.2