[saga.git] / mst.tex

\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Minimum Spanning Trees}

\section{The Problem}

The problem of finding a minimum spanning tree of a weighted graph is one of the
best studied problems in the area of combinatorial optimization and it can be said
that it stood at the cradle of this discipline. Its colorful history (see \cite{graham:msthistory}
and \cite{nesetril:history} for the full account) begins in~1926 with
the pioneering work of Bor\accent23uvka
\cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
who studied primarily an Euclidean version of the problem related to planning
of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
algorithm for the general version of the problem. As it was well before the birth of graph
theory, the language of his paper was complicated, so we will rather state the problem
in contemporary terminology:

\proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
find its minimum spanning tree, where:

\defn\thmid{mstdef}%
For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
\itemize\ibull
\:A~tree $T$ is a \df{spanning tree} of~$G$ if and only if $V(T)=V(G)$ and $E(T)\subseteq E(G)$.
\:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
\:A~spanning tree~$T$ is \df{minimal} iff $w(T)$ is the smallest possible of all spanning trees.
  We use an abbreviation \df{MST} for such trees.
\:For a disconnected graph, a \df{(minimal) spanning forest (MSF)} is defined as
  a union of (minimal) spanning trees of its connected components.
\endlist

Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
mostly geometric setting, giving another polynomial algorithm. However, when
computer science and graph theory started forming in the 1950's and the
spanning tree problem was one of the central topics of the flourishing new
disciplines, the previous work was not well known and the algorithms have been
rediscovered several times.

Recently, several significantly faster algorithms were discovered, most notably the
$\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
and Pettie \cite{pettie:ackermann}.

\FIXME{Write the rest of the history.}

This chapter attempts to survery the important algorithms for finding the MST and it
also presents several new ones.

\section{Basic Properties}

In this section, we will examine the basic properties of spanning trees and prove
several important theorems to base the algorithms upon. We will follow the theory
developed by Tarjan in~\cite{tarjan:dsna}.

For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all other
graphs will be subgraphs of~$G$ containing all of its vertices. We will use the
same notation for the subgraph and for the corresponding set of edges.

First of all, let us show that the weights on edges are not necessary for the
definition of the MST. We can formulate an equivalent characterization using
an ordering of edges instead.

\defnn{Heavy and light edges}\thmid{heavy}%
Let~$T$ be a~spanning tree. Then:
\itemize\ibull
\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
\:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
  the edges of this path \df{edges covered by~$e$}.
\:An edge~$e$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there
  is an edge $f\in T[e]$ such that $w(f) > w(e)$.
\:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light.
\endlist

\rem
Please note that the above properties also apply to tree edges
which by definition cover only themselves and therefore they are always heavy.

\lemman{Light edges}\thmid{lightlemma}%
Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
is not minimal.

\proof
If there is a $T$-light edge~$e$, then there exists an edge $f\in T[e]$ such
that $w(f)>w(e)$. Now $T-f$ is a forest of two trees with endpoints of~$e$
located in different components, so adding $e$ to this forest must restore
connectivity and $T':=T-f+e$ is another spanning tree with weight $w(T')
= w(T)-w(f)+w(e) < w(T)$. Hence $T$ could not have been minimal.
\qed

\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}}

The converse of this lemma is also true and to prove it, we will once again use
technique of transforming trees by \df{exchanges} of edges. In the proof of the
lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
a spanning tree for another edge~$f$ covered by~$e$, the result is again
a spanning tree. In fact, it is possible to transform any spanning tree
to any other spanning tree by a sequence of exchanges.

\lemman{Exchange property for trees}\thmid{xchglemma}%
Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
a sequence of edge exchanges which transforms $T$ to~$T'$. More formally,
there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
$T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.

\proof
By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, then
both trees are identical and an empty sequence suffices. Otherwise, the trees are different,
but they are of the same size, so there must exist an edge $e'\in T'\setminus T$.
The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
\qed

\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}}

\lemman{Monotone exchanges}\thmid{monoxchg}%
Let $T$ be a spanning tree such that there are no $T$-light edges and $T$
be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
transforming $T$ to~$T'$ such that the weight does not increase in any step.

\proof
We improve the argument from the previous proof, refining the induction step.
When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
the weight never drops, since $e'$ is not a $T$-light edge and therefore
$w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\le w(T)$.

To allow the induction to proceed, we have to make sure that there are still
no light edges with respect to~$T^*$. In fact, it is enough to avoid $T^*$-light
edges in $T'\setminus T^*$, since these are the only edges considered by the
induction step. Instead of picking $e'$ arbitrarily, we will pick the lightest
edge available. Now consider an edge $f\in T'\setminus T^*$. We want to show
that $f$ is heavier than all edges on $T^*[f]$.

The path $T^*[f]$ is either the original path $T[f]$ (if $e\not\in T[f]$)
or $T[f] \symdiff C$, where $C$ is the cycle $T[e']+e$. The first case is
trivial, in the second case $w(f)\ge w(e')$ and all other edges on~$C$
are lighter than~$e'$.
\qed

\theorem
A~spanning tree~$T$ is minimal iff there is no $T$-light edge.

\proof
If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light
edges.
Conversely, when $T$ is a spanning tree without $T$-light edges
and $T_{min}$ is an arbitrary minimal spanning tree, then according to the Monotone
exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
and thus $T$~is also minimal.
\qed

In general, a single graph can have many minimal spanning trees (for example
a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$
minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
However, as the following lemma shows, this is possible only if the weight
function is not injective.

\lemman{MST uniqueness}
If all edge weights are distinct, then the minimum spanning tree is unique.

\proof
Consider two minimal spanning trees $T_1$ and~$T_2$. According to the previous
theorem, there are no light edges with respect to neither of them, so by the
Monotone exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
of edge exchanges going from $T_1$ to $T_2$. Each exchange in this sequence is
strictly increasing, because all edge weights all distinct. On the other hand,
we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
$T_1$ and $T_2$ must be identical.
\qed

\rem\thmid{edgeoracle}%
To simplify the description of MST algorithms, we will expect that the input
graph has all edge weights distinct. We will also assume that instead of explicit
edge weights we will be given a comparison oracle, that is a function which answers
questions ``$w(e)<w(f)$?'' in constant time. Please note that this is without loss
of generality, because when some edges have identical weights, we can determine their
relative order by comparing some unique identifiers of these edges and every MST
of the new graph will be also a MST of the original one.
In the few cases where we need a more concrete input, we will explicitly say so.

\section{The Red-Blue Meta-Algorithm}

Most MST algorithms can be described as special cases of the following procedure
(again following \cite{tarjan:dsna}):

\algn{Red-Blue Meta-Algorithm}
\algo
\algin A~graph $G$ with an edge comparison oracle (see \thmref{edgeoracle})
\:In the beginning, all edges are colored black.
\:While possible, use one of the following rules:
\::Pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue. \cmt{Blue rule}
\::Pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge red. \cmt{Red rule}
\algout Minimum spanning tree of~$G$ consisting of edges colored blue.
\endalgo

\rem
This is not a proper algorithm, since the selection of rules to apply is not specified.
We will however prove that for any such selection the procedure stops with the correct result.
Also, it will turn out that each of the classical MST algorithms can be stated as a
specific rule selection strategy of this procedure, which justifies the name
meta-algorithm for it.

\lemman{Blue lemma}
When an edge is colored blue in any step of the procedure, it is contained in the minimum spanning tree.

\proof
\qed

\lemman{Red lemma}
When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.

\proof
\qed

\figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}

\lemman{Black lemma}
As long as there exists a black edge, at least one rule can be applied.

\proof
\qed

\figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}

\theoremn{Red-Blue correctness}
For any selection of rules, the Red-Blue procedure stops and the blue edges form
the minimum spanning tree of the input graph.

\proof
\qed



% mention Steiner trees
% mention matroids
% sorted weights

\endpart