Fixed missing ref.

[saga.git] / appl.tex

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

\chapter{Applications}

\section{Special cases and related problems}

Towards the end of our story of the minimum spanning trees, we will now focus our attention
on various special cases of the MST problem and also to several related problems that
frequently arise in practice.

\paran{Graphs with sorted edges}\id{sortededges}%
When the edges of the given graph are already sorted by their weights, we can use the Kruskal's
algorithm to find the MST in time $\O(m\timesalpha(n))$ (Theorem \ref{kruskal}).
We can however do better: As the minimality of a~spanning tree depends only on the
order of weights and not on the actual values (The Minimality Theorem, \ref{mstthm}), we can
renumber the weights to $1, \ldots, m$ and find the MST using the Fredman-Willard
algorithm for integer weights. According to Theorem \ref{intmst} it runs in
time $\O(m)$ on the Word-RAM.

\paran{Graphs with a~small number of distinct weights}
When the weights of edges are drawn from a~set of a~fixed size~$U$, we can
sort them in linear time and so reduce the problem to the previous case.
A~more practical way is to use the Jarn\'\i{}k's algorithm (\ref{jarnimpl}),
but replace the heap by an~array of $U$~buckets. As the number of buckets
is constant, we can find the minimum in constant time and hence the whole
algorithm runs in time $\O(m)$, even on the Pointer Machine. For large
values of~$U,$ we can build a~binary search tree or the van Emde-Boas
tree (see Section \ref{ramdssect} and \cite{boas:vebt}) on the top of the buckets to bring the complexity
of finding the minimum down to $\O(\log U)$ or $\O(\log\log U)$ respectively.

\paran{Graphs with floating-point weights}
A~common case of non-integer weights are rational numbers in floating-point (FP)
representation. Even in this case we will be able to find the MST in linear time.
The most common representation of binary FP numbers specified by the IEEE
standard 754-1985 \cite{ieee:binfp} has a~useful property:  When the
bit strings encoding non-negative FP numbers are read as ordinary integers,
the order of these integers is the same as of the original FP numbers. We can
therefore once again replace the edge weights by integers and use the linear-time
integer algorithm. While the other FP representations (see \cite{dgoldberg:fp} for
an~overview) need not have this property, the corresponding integers can be adjusted
in $\O(1)$ time to the format we need using bit masking. (More advanced tricks of this type have been
employed by Thorup \cite{thorup:floatint} to extend his linear-time algorithm
for single-source shortest paths to FP edge lengths.)

\paran{Graphs with bounded degrees}
For graphs with vertex degrees bounded by a~constant~$\Delta$, the problem is either
trivial (if $\Delta<3$) or as hard as for arbitrary graphs. There is a~simple linear-time
transform of arbitrary graphs to graphs with maximum degree~3 which preserves the MST:

\lemman{Degree reduction}\id{degred}%
For every graph~$G$ there exists a~graph~$G'$ with maximum degree at most~3 and
a~function $\pi: E(G)\rightarrow E(G')$ such that $\mst(G) = \pi^{-1}(\mst(G'))$.
The graph $G'$ and the embedding~$\pi$ can be constructed in time $\O(m)$.

\figure{french.eps}{\epsfxsize}{Degree reduction in Lemma~\ref{degred}}

\proof
We show how to eliminate a~single vertex~$v$ of degree $d>3$ and then apply
induction.

Assume that $v$~has neighbors $w_1,\ldots,w_d$. We replace~$v$ and the edges~$vw_i$
by $d$~new vertices $v_1,\ldots,v_d$, joined by a~path $v_1v_2\ldots v_d$, and
edges~$v_iw_i$. Each edge of the path will receive a~weight smaller than all
original weights, the other edges will inherit the weights of the edges $vw_i$
they replace. The edges of the path will therefore lie in the MST (this is
obvious from the Kruskal's algorithm) and as~$G$ can be obtained from the
new~$G'$ by contracting the path, the rest follows from the Contraction lemma
(\ref{contlemma}).

This step can be carried out in time $\O(d)$. It replaces a high-degree
vertex by vertices of degree~3 and it does not change degrees of any other
vertices. So the whole procedure stops in at most~$n$ such
steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$, including the
time needed to find the high-degree vertices at the beginning.
\qed

\paran{Euclidean MST}
The MST also has its counterparts in the realm of geometric algorithms. Suppose
that we have $n$~points $x_1,\ldots,x_n$ in the plane and we want to find the
shortest system of segments connecting these points. If we want the segments to
touch only in the given points, this is equivalent to finding the MST of the
complete graph on the vertices $V=\{x_1,\ldots,x_n\}$ with edge weights
defined as the Euclidean distances of the points. Since the graph is dense, many of the MST
algorithms discussed run in linear time with the size of the graph, hence
in time $\O(n^2)$.

There is a~more efficient method based on the observation that the MST
is always a~subgraph of the Delaunay's tesselation for the given points
(this was first noted by Shamos and Hoey \cite{shamos:closest}). The
tesselation is a~planar graph, which guarantees that it has $\O(n)$ edges,
and it is a~dual graph of the Voronoi diagram of the given points, which can
be constructed in time $\O(n\log n)$ using for example the Fortune's
algorithm \cite{fortune:voronoi}. We can therefore reduce the problem
to finding the MST of the tesselation for which $\O(n\log n)$ time
is more than sufficient.

This approach fails for non-Euclidean metrics, but in some cases
(in particular for the rectilinear metric) the $\O(n\log n)$ time bound
is also achievable by the algorithm of Zhou et al.~\cite{zhou:nodel}
based on the sweep-line technique and the Red rule. For other
variations on the geometric MST, see Eppstein's survey paper
\cite{eppstein:spanning}.

\paran{Steiner trees}
The constraint that the segments in the previous example are allowed to touch
each other only in the given points looks artificial and it is indeed uncommon in
practical applications (including the problem of designing electrical transmission
lines originally studied by Bor\o{u}vka). If we lift this restriction, we get
the problem known by the name Steiner tree.\foot{It is named after the Swiss mathematician
Jacob Steiner who studied a~special case of this problem in the 19th century.}
We can also define it in terms of graphs:

\defn A~\df{Steiner tree} of a~weighted graph~$(G,w)$ with a~set~$M\subseteq V$
of \df{mandatory vertices} is a~tree~$T\subseteq G$ that contains all the mandatory
vertices and its weight is minimum possible.

When $M=V$, the Steiner tree is identical to the MST, but if we allow an~arbitrary
choice of the mandatory vertices, it is NP-hard. This has been proven by Garey and Johnson
\cite{garey:steiner,garey:rectisteiner} for not only the graph version with
weights $\{1,2\}$, but also for the planar version with Euclidean or rectilinear
metric. There is a~polynomial-time approximation algorithm with ratio $5/3$ for
graphs due to Pr\"omel and Steger \cite{proemel:steiner} and a~polynomial-time
approximation scheme for the Euclidean Steiner tree in an~arbitrary dimension
by Arora \cite{arora:tspapx}.

\paran{Approximating the weight of the MST}
Sometimes we are not interested in the actual edges forming the MST and only
the weight matters. If we are willing to put up with a~randomized approximation,
we can even achieve sub-linear complexity. Chazelle et al.~\cite{chazelle:mstapprox}
have shown an~algorithm which, given $0 < \varepsilon < 1/2$, approximates
the weight of the MST of a~graph with average degree~$d$ and edge weights from the set
$\{1,\ldots,w\}$ in time $\O(dw\varepsilon^{-2}\cdot\log(dw/\varepsilon))$,
producing a~weight which has relative error at most~$\varepsilon$ with probability
at least $3/4$. They have also proven a~close lower bound $\Omega(dw\varepsilon^{-2})$.

For the $d$-dimensional Euclidean case, there is a~randomized approximation
algorithm by Czumaj et al.~\cite{czumaj:euclidean} which with high probability
produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\sqrt{n}\cdot \poly(1/\varepsilon))$\foot{%
$\widetilde\O(f) = \O(f\cdot\log^{\O(1)} f)$ and $\poly(n)=n^{\O(1)}$.}
queries to a~data structure containing the points. The data structure is expected
to answer orthogonal range queries and cone approximate nearest neighbor queries.
There is also an~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation
algorithm for the MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}.
(This is still sub-linear since the corresponding graph has roughly $n^2$ edges.)

%--------------------------------------------------------------------------------

\section{Practical algorithms}

So far, we were studying the theoretical aspects of the MST algorithms.
How should we find the MST on a~real computer?

Moret and Shapiro \cite{moret:expmst} have conducted an~extensive experimental
study of performance of implementations of various MST algorithms on different
computers. They have tested the algorithms on several sets of graphs, varying
in the number of vertices (up to millions) and in edge density (from constant to
$n^{1/2}$. In almost all tests, the winner was an~ordinary Prim's algorithm
implemented with pairing heaps \cite{fredman:pairingheap}. The pairing heaps
are known to perform surprisingly well in practice, but they still elude attempts
at complete theoretical analysis. So far the best results are those of Pettie
\cite{pettie:pairing}, who has proven that deletion of the minimum takes $\O(\log n)$
time and all other operations take $\O(2^{2\scriptscriptstyle\sqrt{\log\log n}})$; both bounds are amortized.

The Moret's study however completely misses variants of the Bor\o{u}vka's algorithm
and many of those have very promising characteristics, especially for planar graphs
and minor-closed classes.

Also, Katriel et al.~\cite{katriel:cycle} have proposed a~new algorithm based on~the
Red rule. It is a~randomized algorithm which uses a~simplified form of the idea of edge
filtering from the algorithm of Karger, Klein and Tarjan (see Section \ref{randmst}).
The expected time complexity is slightly worse: $\O(n\log n + m)$. However, for dense
graphs it performs very well in practice, even in comparison with the Moret's results.

\paran{Parallel algorithms}
Most of the early parallel algorithms for the MST are variants of the Bor\o{u}vka's algorithm.
The operations on the individual trees are independent of each other, so they can be carried out in parallel.
There are $\O(\log n)$ steps and each of them can be executed in $\O(\log n)$ parallel time using
standard PRAM techniques (see \cite{jaja:parallel} for the description of the model).

Several better algorithms have been constructed, the best of which run in time $\O(\log n)$.
Chong, Han and Lam \cite{chong:parallel} have recently discovered an~algorithm that achieves
this time complexity even on the EREW PRAM --- the weakest of the parallel RAM's which does
not allow concurrent reading nor writing to the same memory cell by multiple processors.
In this model, the $\O(\log n)$ bound is clearly the best possible.

As in the sequential models, the basic question still remains open: Is it
possible to compute the MST in parallel on EREW PRAM, spending only linear
work? This would of course imply existence of a~linear-time sequential
algorithm, so none of the known parallel algorithms achieve that. Algorithms
with linear work can be obtained by utilizing randomness, as shown for example
by Pettie and Ramachandran \cite{pettie:minirand}, but so far only at the
expense of higher time complexity.

\endpart