Classical ones.

[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 since its birth.
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 dawn of graph
theory, the language of his paper was complicated, so we will better 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, defined as follows:

\defn\thmid{mstdef}%
For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
\itemize\ibull
\:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
\:A~\df{spanning tree} of $G$ is any its spanning subgraph which is a tree.
\:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
  When comparing two weights, we will use the terms \df{lighter} and \df{heavier} in the
  obvious sense.
\:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$
  is the smallest possible of all the spanning trees of~$G$.
\:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as
  a union of (minimum) 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 efficient 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 had to be
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 spanning subgraphs of~$G$. We will use the same notation
for the subgraphs as for the corresponding sets 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{light with respect to~$T$} (or just \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 minimum.

\proof
If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such
that $w(e')>w(e)$. Now $T-e'$ 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-e'+e$ is another spanning tree with weight $w(T')
= w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum.
\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$,
both trees are identical and no exchanges are needed. Otherwise, the trees are different,
but as they are of the same size, 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')\ge w(T)$.

To keep the induction going, we have to make sure that there are still no light
edges with respect to~$T^*$. In fact, it is enough to avoid such edges in
$T'\setminus T^*$, since these are the only edges considered by the induction
steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$
by picking the lightest such edge.

Now consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not
$T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
either equal to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter one
$w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
than~$e'$ as $e'$ was not $T$-light.
\qed

\theorem\thmid{mstthm}%
A~spanning tree~$T$ is minimum iff there is no $T$-light edge.

\proof
If~$T$ is minimum, 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 minimum 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 minimum.
\qed

In general, a single graph can have many minimum 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 theorem shows, this is possible only if the weight
function is not injective.

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

\proof
Consider two minimum 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 sequence of non-decreasing
edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
these edge exchanges must be in fact strictly increasing. 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 weights
of all edges are distinct and that instead of numeric weights (usually accompanied
by problems with representation of real numbers in algorithms) we will be given
a comparison oracle, that is a function which answers questions ``$w(e)<w(f)$?'' in
constant time. In case the weights are not distinct, we can easily break ties by
comparing some unique edge identifiers and according to our characterization of
minimum spanning trees, the unique MST of the new graph will still be a MST of the
original graph. In the few cases where we need a more concrete input, we will
explicitly state 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.
\:Apply rules as long as possible:
\::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
\::Or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \hphantas{red.}{blue.} \cmt{Red rule}
\algout Minimum spanning tree of~$G$ consisting of edges colored blue.
\endalgo

\rem
This procedure is not a proper algorithm, since it does not specify how to choose
the rule to apply. We will however prove that no matter how the rules are applied,
the procedure always stops and gives the correct result. Also, it will turn out
that each of the classical MST algorithms can be described as a specific way
of choosing the rules in this procedure, which justifies the name meta-algorithm.

\proclaim{Notation}%
We will denote the unique minimum spanning tree of the input graph by~$T_{min}$.
We intend to prove that this is also the output of the procedure.

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

\proof
By contradiction. Let $e$ be an edge painted blue as the lightest edge of a cut~$C$.
If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ which is
contained in~$C$ (take any pair of vertices separated by~$C$, the path
in~$T_{min}$ joining these vertices must cross~$C$ at least once). Exchanging
$e$ for $e'$ in $T_{min}$ yields an even lighter spanning tree since
$w(e)<w(e')$. \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
Again by contradiction. Assume that $e$ is an edge painted red as the heaviest edge
of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
lie in different components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields
a lighter spanning tree than $T_{min}$.
\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
Assume that $e=xy$ be a black edge. Let us denote $M$ the set of vertices
reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest
edge on this cycle. This holds because all blue edges have been already proven
to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\thmref{mstthm}).
In this case we can apply the red rule.

On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
and $V(G)\setminus M$ contains no blue edges, therefore we can use the blue rule.
\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
To prove that the procedure stops, let us notice that no edge is ever recolored,
so we must run out of black edges after at most $m$ steps. Recoloring
to the same color is avoided by the conditions built in the rules, recoloring to
a different color would mean that the an edge would be both inside and outside~$T_{min}$
due to our Red and Blue lemmata.

When no further rules can be applied, the Black lemma guarantees that all edges
are colored, so by the Blue lemma all blue edges are in~$T_{min}$ and by the Red
lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
\qed

\section{Classical algorithms}

The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.

\algn{Kruskal \cite{kruskal:mst}}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:Sort edges of~$G$ by their increasing weight.
\:$T\=\emptyset$. \cmt{an empty spanning subgraph}
\:For all edges $e$ in their sorted order:
\::If $T+e$ is acyclic, add~$e$ to~$T$.
\::Otherwise drop~$e$.
\algout Minimum spanning tree~$T$.
\endalgo

\proof
During the course of the algorithm, $T$ is a forest with all edges blue. Adding~$e$ to~$T$
in step~4 applies the Blue rule on the cut separating two components of~$T$ ($e$ is the lightest,
because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds
to the red rule on the cycle found ($e$~must be the heaviest, since all other edges of the
cycle have been already processed). At the end of the algorithm, all edges have been colored,
so~$T$ must be the~MST.
\qed

\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=$ a single-vertex tree containing any vertex of~$G$.
\:While there are vertices outside $T$:
\::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
\::$T\=T+uv$.
\algout Minimum spanning tree~$T$.
\endalgo

\proof
In every step of the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying
the Blue rule to a cut between~$T$ and the rest of the given graph. We need not care about
the remaining edges, since for a connected graph the algorithm always stops with the right
number of blue edges.
\qed

\algn{Bor\accent23uvka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=$ a forest consisting of vertices of~$G$ and no edges.
\:While $T$ is not connected:
\::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
   separating $T_i$ from the rest of~$T$.
\::Add all $e_i$'s to~$T$.
\algout Minimum spanning tree~$T$.
\endalgo

\proof
Again $T$ is a blue forest, because every addition of some edge~$e_i$ to~$T$ is a straightforward
application of the Blue rule. It remains to show that adding the edges simultaneously does not
produce a cycle.
\FIXME{Finish}
\qed

\algn{Contracting version of Bor\accent23uvka's algorithm}

% G has to be connected
% mention Steiner trees
% mention matroids
% sorted weights

\endpart