First bits of verification.

[saga.git] / adv.tex

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

\chapter{Advanced MST Algorithms}

\section{Minor-closed graph classes}\id{minorclosed}%

The contractive algorithm given in section~\ref{contalg} has been found to perform
well on planar graphs, but in the general case its time complexity was not linear.
Can we find any broader class of graphs where the algorithm is still efficient?
The right context turns out to be the minor-closed graph classes, which are
closed under contractions and have bounded density.

\defn\id{minordef}%
A~graph~$H$ is a \df{minor} of a~graph~$G$ (written as $H\minorof G$) iff it can be obtained
from a~subgraph of~$G$ by a sequence of simple graph contractions (see \ref{simpcont}).

\defn
A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and
its every minor~$H$, the graph~$H$ lies in~$\cal C$ as well. A~class~$\cal C$ is called
\df{non-trivial} if at least one graph lies in~$\cal C$ and at least one lies outside~$\cal C$.

\example
Non-trivial minor-closed classes include:
\itemize\ibull
\:planar graphs,
\:graphs embeddable in any fixed surface (i.e., graphs of bounded genus),
\:graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles,
\:graphs of bounded tree-width or path-width.
\endlist

\para
Many of the nice structural properties of planar graphs extend to
minor-closed classes, too (see \cite{lovasz:minors} for a~nice survey
of this theory and \cite{diestel:gt} for some of the deeper results).
The most important property is probably the characterization
of such classes in terms of their forbidden minors.

\defn
For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class
of graphs which do not contain any of the graphs in~$\cal H$ as a~minor.
We will call $\cal H$ the set of \df{forbidden (or excluded) minors} for this class.
We will often abbreviate $\Forb(\{M_1,\ldots,M_n\})$ to $\Forb(M_1,\ldots,M_n)$.

\obs
For every~${\cal H}\ne\emptyset$, the class $\Forb({\cal H})$ is non-trivial
and closed on minors. This works in the opposite direction as well: for every
minor-closed class~$\cal C$ there is a~class $\cal H$ such that ${\cal C}=\Forb({\cal H})$.
One such~$\cal H$ is the complement of~$\cal C$, but smaller ones can be found, too.
For example, the planar graphs can be equivalently described as the class $\Forb(K_5, K_{3,3})$
--- this follows from the Kuratowski's theorem (the theorem speaks of forbidden
subdivisions, but while in general this is not the same as forbidden minors, it
is for $K_5$ and $K_{3,3}$). The celebrated theorem by Robertson and Seymour
guarantees that we can always find a~finite set of forbidden minors.

\thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
For every non-trivial minor-closed graph class~$\cal C$ there exists
a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$.

\proof
This theorem has been proven in a~long series of papers on graph minors
culminating with~\cite{rs:wagner}. See this paper and follow the references
to the previous articles in the series.
\qed

\para
For analysis of the contractive algorithm,
we will make use of another important property --- the bounded density of
minor-closed classes. The connection between minors and density dates back to
Mader in the 1960's and it can be proven without use of the Robertson-Seymour
theorem.

\defn\id{density}%
Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$
to be the infimum of all~$\varrho$'s such that $m(G) \le \varrho\cdot n(G)$
holds for every $G\in\cal C$.

\thmn{Mader \cite{mader:dens}}
For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
of average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph.

\proofsketch
(See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.)

Let us fix~$k$ and prove by induction on~$m$ that every graph of average
degree at least~$2^m$ contains a~subdivision of some graph with $k$~vertices
and ${k\choose 2}\ge m\ge k$~edges. For $m={k\choose 2}$ the theorem follows
as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$.

The base case $m=k$: Let us observe that when the average degree
is~$a$, removing any vertex of degree less than~$a/2$ does not decrease the
average degree. A~graph with $a\ge 2^k$ therefore has a~subgraph
with minimum degree $\delta\ge a/2=2^{k-1}$. Such subgraph contains
a~cycle on more than~$\delta$ vertices, in other words a~subdivision of
the cycle~$C_k$.

Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and
assume that the theorem already holds for $m-1$. Without loss of generality,
$G$~is connected. Consider a~maximal set $U\subseteq V$ such that the subgraph $G[U]$
induced by~$U$ is connected and the graph $G.U$ ($G$~with $U$~contracted to
a~single vertex) has average degree at least~$2^m$ (such~$U$ exists, because
$G=G.U$ whenever $\vert U\vert=1$). Now consider the subgraph~$H$ induced
in~$G$ by the neighbors of~$U$. Every $v\in V(H)$ must have $\deg_H(v) \ge 2^{m-1}$,
as otherwise we can add this vertex to~$U$, contradicting its
maximality. By the induction hypothesis, $H$ contains a~subdivision of some
graph~$R$ with $r$~vertices and $m-1$ edges. Any two non-adjacent vertices
of~$R$ can be connected in the subdivision by a~path lying entirely in~$G[U]$,
which reveals a~subdivision of a~graph with $m$~edges. \qed

\thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
Every non-trivial minor-closed class of graphs has finite edge density.

\proof
Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$.
As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(K_x)$, so
$\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the
theorem for classes excluding a~single complete graph~$K_x$.

We will show that $\varrho({\cal C})\le 2h(x)$, where $h$~is the function
from the previous theorem. If any $G\in{\cal C}$ had more than $2h(x)\cdot n(G)$
edges, its average degree would be at least~$h(x)$, so by the previous theorem
$G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor.
\qed

\rem
Minor-closed classes share many other interesting properties, as shown for
example by Theorem 6.1 of \cite{nesetril:minors}.

\thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}%
For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
algorithm (\ref{contbor}) finds the MST of any graph of this class in time
$\O(n)$. (The constant hidden in the~$\O$ depends on the class.)

\proof
Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered
by the algorithm at the beginning of the $i$-th iteration by~$G_i$ and its number of vertices
and edges by $n_i$ and $m_i$ respectively. Again the $i$-th phase runs in time $\O(m_i)$
and $n_i \le n/2^i$, so it remains to show a linear bound for the $m_i$'s.

Since each $G_i$ is produced from~$G_{i-1}$ by a sequence of edge contractions,
all $G_i$'s are minors of~$G$.\foot{Technically, these are multigraph contractions,
but followed by flattening, so they are equivalent to contractions on simple graphs.}
So they also belong to~$\cal C$ and by the previous theorem $m_i\le \varrho({\cal C})\cdot n_i$.
\qed

\rem\id{nobatch}%
The contractive algorithm uses ``batch processing'' to perform many contractions
in a single step. It is also possible to perform contractions one edge at a~time,
batching only the flattenings. A~contraction of an edge~$uv$ can be done
in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back
with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small
degrees. The following lemma shows that this is always the case in minor-closed
classes.

\lemman{Low-degree vertices}\id{lowdeg}%
Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph
with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$.

\proof
Assume the contrary: Let there be at least $n/2$ vertices with degree
greater than~$4\varrho$.  Then $\sum_v \deg(v) > n/2
\cdot 4\varrho = 2\varrho n$, which is in contradiction with the number
of edges being at most $\varrho n$.
\qed

\rem
The proof can be also viewed
probabilistically: let $X$ be the degree of a vertex of~$G$ chosen uniformly at
random. Then ${\bb E}X \le 2\varrho$, hence by the Markov's inequality
${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have
$\deg(v)\le 4\varrho$.

\algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}%
\algo
\algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
\:$T\=\emptyset$.
\:$\ell(e)\=e$ for all edges~$e$.
\:While $n(G)>1$:
\::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
\:::Select the lightest edge~$e$ incident with~$v$.
\:::Contract~$G$ along~$e$.
\:::$T\=T + \ell(e)$.
\::Flatten $G$, removing parallel edges and loops.
\algout Minimum spanning tree~$T$.
\endalgo

\thm
When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the
Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$ 
finds the MST of any graph from this class in time $\O(n)$. (The constant
in the~$\O$ depends on~the class.)

\proof
Let us denote by $G_i$, $n_i$ and $m_i$ the graph considered by the
algorithm at the beginning of the $i$-th iteration of the outer loop,
and the number of its vertices and edges respectively. As in the proof
of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s
are minors of the graph~$G$ given as the input.

For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
have degree at most~$t$. Each selected edge removes one such vertex and
possibly increases the degree of another, so at least $n_i/4$ edges get selected.
Hence $n_i\le 3/4\cdot n_{i-1}$ and therefore $n_i\le n\cdot (3/4)^i$ and the
algorithm terminates after $\O(\log n)$ iterations.

Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
the trivial cut $\delta(v)$ (see the Blue Rule in \ref{rbma}).
The steps 6 and~7 therefore correspond to the operation
described by the Lemma on contraction of MST edges (\ref{contlemma}) and when
the algorithm stops, $T$~is indeed the minimum spanning tree.

It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have
$m_i\le \varrho n_i \le \varrho n/2^i$.
We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$.
Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting
Bor\o{u}vka's Algorithm (see \ref{contiter}).

The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
\qed

\rem
For planar graphs, we can get a sharper version of the low-degree lemma,
showing that the algorithm works with $t=8$ as well (we had $t=12$ as
$\varrho=3$). While this does not change the asymptotic time complexity
of the algorithm, the constant-factor speedup can still delight the hearts of
its practical users.

\lemman{Low-degree vertices in planar graphs}%
Let $G$ be a planar graph with $n$~vertices. Then at least $n/2$ vertices of~$v$
have degree at most~8.

\proof
It suffices to show that the lemma holds for triangulations (if there
are any edges missing, the situation can only get better) with at
least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$.
The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
so by the same argument as in the proof of the general lemma, for at least $n/2$
vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$.
\qed

\rem\id{hexa}%
The constant~8 in the previous lemma is the best we can have.
Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them
lie on the outer face and have degrees at most~6, the remaining $n-\O(k)$ interior
vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$,
ignoring terms of order $\O(k)$. All interior triangles can be properly colored with
two colors, black and white. Now add a~new vertex inside each white face and connect
it to all three vertices on the boundary of that face. This adds $f/2 \approx n$
vertices of degree~3 and it increases the degrees of the original $\approx n$ interior
vertices to~9, therefore about a half of the vertices of the new planar graph
has degree~9.

\figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}

\rem
The observation in~Theorem~\ref{mstmcc} was also made by Gustedt in~\cite{gustedt:parallel},
who studied a~parallel version of the contractive Bor\o{u}vka's algorithm applied
to minor-closed classes.

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

\section{Using Fibonacci heaps}
\id{fibonacci}

We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
Fredman and Tarjan have shown a~faster implementation in~\cite{ft:fibonacci}
using their Fibonacci heaps. In this section, we convey their results and we
show several interesting consequences.

The previous implementation of the algorithm used a binary heap to store all edges
separating the current tree~$T$ from the rest of the graph, i.e., edges of the cut~$\delta(T)$.
Instead of that, we will remember the vertices adjacent to~$T$ and for each such vertex~$v$ we
will maintain the lightest edge~$uv$ such that $u$~lies in~$T$. We will call these edges \df{active edges}
and keep them in a~Fibonacci heap, ordered by weight.

When we want to extend~$T$ by the lightest edge of~$\delta(T)$, it is sufficient to
find the lightest active edge~$uv$ and add this edge to~$T$ together with the new vertex~$v$.
Then we have to update the active edges as follows. The edge~$uv$ has just ceased to
be active. We scan all neighbors~$w$ of the vertex~$v$. When $w$~is in~$T$, no action
is needed. If $w$~is outside~$T$ and it was not adjacent to~$T$ (there is no active edge
remembered for it so far), we set the edge~$vw$ as active. Otherwise we check the existing
active edge for~$w$ and replace it by~$vw$ if the new edge is lighter.

The following algorithm shows how these operations translate to insertions, decreases
and deletions on the heap.

\algn{Active Edge Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}%
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$v_0\=$ an~arbitrary vertex of~$G$.
\:$T\=$ a tree containing just the vertex~$v_0$.
\:$H\=$ a~Fibonacci heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(uv)$, initially empty.
\:$A\=$ a~mapping of vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
\:\<Insert> all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly.
\:While $H$ is not empty:
\::$(u,v)\=\<DeleteMin>(H)$.
\::$T\=T+uv$.
\::For all edges $vw$ such that $w\not\in T$:
\:::If there exists an~active edge~$A(w)$:
\::::If $vw$ is lighter than~$A(w)$, \<Decrease> $A(w)$ to~$(v,w)$ in~$H$.
\:::If there is no such edge, then \<Insert> $(v,w)$ to~$H$ and set~$A(w)$.
\algout Minimum spanning tree~$T$.
\endalgo

\para
To analyze the time complexity of this algorithm, we will use the standard
theorem on~complexity of the Fibonacci heap:

\thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations
with the indicated amortized time complexities:
\itemize\ibull
\:\<Insert> (insertion of a~new element) in $\O(1)$,
\:\<Decrease> (decreasing value of an~existing element) in $\O(1)$,
\:\<Merge> (merging of two heaps into one) in $\O(1)$,
\:\<DeleteMin> (deletion of the minimal element) in $\O(\log n)$,
\:\<Delete> (deletion of an~arbitrary element) in $\O(\log n)$,
\endlist
\>where $n$ is the number of elements present in the heap at the time of
the operation.

\proof
See Fredman and Tarjan \cite{ft:fibonacci} for both the description of the Fibonacci
heap and the proof of this theorem.
\qed

\thm
Algorithm~\ref{jarniktwo} with the Fibonacci heap finds the MST of the input graph in time~$\O(m+n\log n)$.

\proof
The algorithm always stops, because every edge enters the heap~$H$ at most once.
As it selects exactly the same edges as the original Jarn\'\i{}k's algorithm,
it gives the correct answer.

The time complexity is $\O(m)$ plus the cost of the heap operations. The algorithm
performs at most one \<Insert> or \<Decrease> per edge and exactly one \<DeleteMin>
per vertex. There are at most $n$ elements in the heap at any given time,
thus by the previous theorem the operations take $\O(m+n\log n)$ time in total.
\qed

\cor
For graphs with edge density at least $\log n$, this algorithm runs in linear time.

\rem
We can consider using other kinds of heaps which have the property that inserts
and decreases are faster than deletes. Of course, the Fibonacci heaps are asymptotically
optimal (by the standard $\Omega(n\log n)$ lower bound on sorting by comparisons, see
for example \cite{clrs}), so the other data structures can improve only
multiplicative constants or offer an~easier implementation.

A~nice example is a~\df{$d$-regular heap} --- a~variant of the usual binary heap
in the form of a~complete $d$-regular tree. \<Insert>, \<Decrease> and other operations
involving bubbling the values up spend $\O(1)$ time at a~single level, so they run
in~$\O(\log_d n)$ time. \<Delete> and \<DeleteMin> require bubbling down, which incurs
comparison with all~$d$ sons at every level, so they spend $\O(d\log_d n)$.
With this structure, the time complexity of the whole algorithm
is $\O(nd\log_d n + m\log_d n)$, which suggests setting $d=m/n$, yielding $\O(m\log_{m/n}n)$.
This is still linear for graphs with density at~least~$n^{1+\varepsilon}$.

Another possibility is to use the 2-3-heaps \cite{takaoka:twothree} or Trinomial
heaps \cite{takaoka:trinomial}. Both have the same asymptotic complexity as Fibonacci
heaps (the latter even in the worst case, but it does not matter here) and their
authors claim faster implementation. For integer weights, we can use Thorup's priority
queues described in \cite{thorup:pqsssp} which have constant-time \<Insert> and \<Decrease>
and $\O(\log\log n)$ time \<DeleteMin>. (We will however omit the details since we will
show a~faster integer algorithm soon.)

\para
As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time
for sufficiently dense graphs. In some cases, it is useful to combine it with
another MST algorithm, which identifies a~part of the MST edges and contracts
the graph to increase its density. For example, we can perform several
iterations of the Contractive Bor\o{u}vka's algorithm and find the rest of the
MST by the Active Edge Jarn\'\i{}k's algorithm.

\algn{Mixed Bor\o{u}vka-Jarn\'\i{}k}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:Run $\log\log n$ iterations of the Contractive Bor\o{u}vka's algorithm (\ref{contbor}),
  getting a~MST~$T_1$.
\:Run the Active Edge Jarn\'\i{}k's algorithm (\ref{jarniktwo}) on the resulting
  graph, getting a~MST~$T_2$.
\:Combine $T_1$ and~$T_2$ to~$T$ as in the Contraction lemma (\ref{contlemma}).
\algout Minimum spanning tree~$T$.
\endalgo

\thm
The Mixed Bor\o{u}vka-Jarn\'\i{}k algorithm finds the MST of the input graph in time $\O(m\log\log n)$.

\proof
Correctness follows from the Contraction lemma and from the proofs of correctness of the respective algorithms.
As~for time complexity: The first step takes $\O(m\log\log n)$ time
(by Lemma~\ref{contiter}) and it gradually contracts~$G$ to a~graph~$G'$ of size
$m'\le m$ and $n'\le n/\log n$. The second step then runs in time $\O(m'+n'\log n') = \O(m)$
and both trees can be combined in linear time, too.
\qed

\para
Actually, there is a~much better choice of the algorithms to combine: use the
Active Edge Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while.
A~good choice of the stopping condition is to place a~limit on the size of the heap.
We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
we conserve the current tree and start with a~different vertex and an~empty heap. When this
process runs out of vertices, it has identified a~sub-forest of the MST, so we can
contract the graph along the edges of~this forest and iterate.

\algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=\emptyset$. \cmt{edges of the MST}
\:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
\:$m_0\=m$.
\:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
\::$F\=\emptyset$. \cmt{forest built in the current phase}
\::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
\::While there is a~vertex $v_0\not\in F$:
\:::Run the Active Edge Jarn\'\i{}k's algorithm (\ref{jarniktwo}) from~$v_0$, stop when:
\::::all vertices have been processed, or
\::::a~vertex of~$F$ has been added to the tree, or
\::::the heap has grown to more than~$t$ elements.
\:::Denote the resulting tree~$R$.
\:::$F\=F\cup R$.
\::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
\::Contract~$G$ along all edges of~$F$ and flatten it.
\algout Minimum spanning tree~$T$.
\endalgo

\nota
For analysis of the algorithm, let us denote the graph entering the $i$-th
phase by~$G_i$ and likewise with the other parameters. Let the trees from which
$F_i$~has been constructed be called $R_i^1, \ldots, R_i^{z_i}$. The
non-indexed $G$, $m$ and~$n$ will correspond to the graph given as~input.

\para
However the choice of the parameter~$t$ can seem mysterious, the following
lemma makes the reason clear:

\lemma\id{ijphase}%
The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$.

\proof
During the phase, the heap always contains at most~$t_i$ elements, so it takes
time~$\O(\log t_i)=\O(m/n_i)$ to delete an~element from the heap. The trees~$R_i^j$
are edge-disjoint, so there are at most~$n_i$ \<DeleteMin>'s over the course of the phase.
Each edge is considered at most twice (once per its endpoint), so the number
of the other heap operations is~$\O(m_i)$. Together, it equals $\O(m_i + n_i\log t_i) = \O(m_i+m) = \O(m)$.
\qed

\lemma
Unless the $i$-th phase is final, the forest~$F_i$ consists of at most $2m_i/t_i$ trees.

\proof
As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient
to establish that there are at least~$t_i$ edges incident with every such tree, including
connecting two vertices of the tree.

The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the possibilities
how the algorithm could have stopped growing the tree~$R_i^j$:
\itemize\ibull
\:the heap had more than~$t_i$ elements (step~10): since the each elements stored in the heap
  corresponds to a~unique edges incident with~$R_i^j$, we have enough such edges;
\:the algorithm just added a~vertex of~$F_i$ to~$R_i^j$ (step~9): in this case, an~existing
  tree of~$F_i$ is extended, so the number of edges incident with it cannot decrease;\foot{%
  This is the place where we needed to count the interior edges as well.}
\:all vertices have been processed (step~8): this can happen only in the final phase.
\qeditem
\endlist

\thm\id{itjarthm}%
The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n \le m/n \}$.

\proof
Phases are finite and in every phase at least one edge is contracted, so the outer
loop is eventually terminated. The resulting subgraph~$T$ is equal to $\mst(G)$, because each $F_i$ is
a~subgraph of~$\mst(G_i)$ and the $F_i$'s are glued together according to the Contraction
lemma (\ref{contlemma}).

Let us bound the sizes of the graphs processed in the individual phases. As the vertices
of~$G_{i+1}$ correspond to the components of~$F_i$, by the previous lemma $n_{i+1}\le
2m_i/t_i$. Then $t_{i+1} = 2^{\lceil 2m/n_{i+1} \rceil} \ge 2^{2m/n_{i+1}} \ge 2^{2m/(2m_i/t_i)} = 2^{(m/m_i)\cdot t_i} \ge 2^{t_i}$,
therefore:
$$
\left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\rddots^{\scriptstyle m/n}}}} $}}\;\right\}
\,\hbox{a~tower of~$i$ exponentials.}
$$
As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time
there is enough space in the heap to process the whole graph. So~there are
at most~$\beta(m,n)$ phases and we already know (Lemma~\ref{ijphase}) that each
phase runs in linear time.
\qed

\cor
The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.

\proof
$\beta(m,n) \le \beta(1,n) = \log^* n$.
\qed

\cor
When we use the Iterated Jarn\'\i{}k's algorithm on graphs with edge density
at least~$\log^{(k)} n$ for some $k\in{\bb N}^+$, it runs in time~$\O(km)$.

\proof
If $m/n \ge \log^{(k)} n$, then $\beta(m,n)\le k$.
\qed

\obs
The algorithm spends most of the time in phases which have small heaps. Once the
heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
to guarantee that at most~$k$ phases remain. This means that if we are able to
construct a~heap of size $\Omega(\log^{(k)} n)$ with constant time per operation,
we can get a~linear-time algorithm for MST. This is the case when the weights are
integers:

\thmn{MST for graphs with integer weights, Fredman and Willard \cite{fw:transdich}}\id{intmst}%
MST of a~graph with integer edge weights can be found in time $\O(m)$ on the Word-RAM.

\proof
We will combine the Iterated Jarn\'\i{}k's algorithm with the Q-heaps from section \ref{qheaps}.
We modify the first pass of the algorithm to choose $t=\log n$ and use the Q-heap tree instead
of the Fibonacci heap. From Theorem \ref{qh} and Remark \ref{qhtreerem} we know that the
operations on the Q-heap tree run in constant time, so the modified first phase takes time~$\O(m)$.
Following the analysis of the original algorithm in the proof of Theorem \ref{itjarthm} we obtain
$t_2\ge 2^{t_1} = 2^{\log n} = n$, so the algorithm stops after the second phase.\foot{%
Alternatively, we can use the Q-heaps directly with $k=\log^{1/4}n$ and then stop
after the third phase.}
\qed

\rem
Gabow et al.~\cite{gabow:mst} have shown how to speed up the Iterated Jarn\'\i{}k's algorithm to~$\O(m\log\beta(m,n))$.
They split the adjacency lists of the vertices to small buckets, keep each bucket
sorted and consider only the lightest edge in each bucket until it is removed.
The mechanics of the algorithm is complex and there is a~lot of technical details
which need careful handling, so we omit the description of this algorithm.

\FIXME{Reference to Chazelle.}

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

\section{Verification of minimality}

Now we will turn our attention to a~slightly different problem: given a~spanning
tree, how to verify that it is minimal? We will show that this can be achieved
in linear time and it will serve as a~basis for the randomized linear-time
MST algorithm in the next section.

MST verification has been studied by Koml\'os \cite{komlos:verify}, who has
proven that $\O(m)$ edge comparisons are sufficient, but his algorithm needed
superlinear time to find the edges to compare. Dixon, Rauch and Tarjan
have later shown in \cite{dixon:verify} that the overhead can be reduced
to linear time on the RAM using preprocessing and table lookup on small
subtrees. This algorithm was then simplified by King in \cite{king:verifytwo}.
We will follow the results of Koml\'os and King, but as we have the power of the
RAM data structures from Section~\ref{bitsect} at our command, we will not have
to worry about much technical details.

To verify that a~spanning~$T$ is minimal, it is sufficient to check that all
edges outside~$T$ are $T$-heavy (by Theorem \ref{mstthm}). In fact, we will be
able to find all $T$-light edges efficiently. For each edge $uv\in E\setminus T$,
we will find the heaviest edge of the tree path $T[u,v]$ and compare its weight
to $w(uv)$. It is therefore sufficient to solve this problem:

\problem
Given a~weighted tree~$T$ and a~set of \df{query paths} $Q \subseteq \{ T[u,v] ; u,v\in V(T) \}$
specified by their endpoints, find the heaviest edge for every path in~$Q$.

\para
Finding the heaviest edges can be burdensome if the tree~$T$ is degenerated,
so we will first reduce it to the same problem on a~balanced tree. We run
the Bor\o{u}vka's algorithm on~$T$, which certainly produces $T$ itself, and we
record the order in which the subtrees have been merged in another tree~$B(T)$.
The queries on~$T$ can be then easily translated to queries on~$B(T)$.

\defn
For a~weighted tree~$T$ we define its \df{Bor\o{u}vka tree} $B(T)$ which records
the execution of the Bor\o{u}vka's algorithm run on~$T$. The leaves of $B(T)$
are exactly the vertices of~$T$, every internal vertex~$v$ at level~$i$ from the bottom
corresponds to a~component tree~$C(v)$ formed in the $i$-th phase of the algorithm. When
a~tree $C(v)$ selects an adjacent edge~$xy$ and gets merged with some other trees to form
a~component $C(u)$, we add an~edge $uv$ to~$B(T)$ and set its weight to $w(xy)$.

\obs
As the algorithm finishes with a~single component after the last phase, the Bor\o{u}vka tree
is really a~tree. All its vertices are on the same level and each internal vertex has
at least two sons. Such trees will be called \df{complete branching trees.}

\lemma
For every pair of vertices $x,y\in V(T)$, the heaviest edge of the path $T[x,y]$
has the same weight as the heaviest edge of~$B(T)[x,y]$.

\proof
\qed

\para
We will make one more simplification: For an~arbitrary tree~$T$, we split each
query path $T[x,y]$ to two half-paths $T[x,a]$ and $T[a,y]$ where~$a$ is the
lowest common ancestor of~$x$ and~$y$ in~$T$. It is therefore sufficient to
consider only paths which connect a~vertex with one of its ancestors.

Finding the common ancestors is not trivial, but Harel and Tarjan have shown
in \cite{harel:nca} that linear time is sufficient on the RAM. Several more
accessible algorithms have been developed since then (see the Alstrup's survey
paper \cite{alstrup:nca} and a~particularly elegant algorithm shown by Bender
and Falach-Colton in \cite{bender:lca}). Any of them implies the following
theorem:

\thmn{Lowest common ancestors}\id{lcathm}%
On the RAM, it is possible to preprocess a~tree~$T$ in time $\O(n)$ and then
answer lowest common ancestor queries presented online in constant time.

\proof
See for example Bender and Falach-Colton \cite{bender:lca}.
\qed

\para
We summarize the reductions in the following lemma, also showing that they can
be performed in linear time:

\lemma
For each tree~$T$ and a~set of query paths~$Q$ on~$T$, it is possible to find
a~complete branching tree~$T'$ in linear time together with a~set~$Q'$ of query
paths on~$T'$, such that the weights of the heaviest edges of the new paths can
be transformed to the weights of the heaviest edges of the paths in~$Q$ in
linear time.
The tree $T$ has at most $2n(T)$ vertices. The set~$Q'$ contains
at most~$2\vert Q\vert$ paths and each of them connects a~vertex of~$T'$ with one
of its ancestors.

\proof
The tree~$T'$ will be the Bor\o{u}vka tree for~$T$. We run the contractive version
of the Bor\o{u}vka's algorithm (Algorithm \ref{contbor}) on~$T$. It runs in linear time,
for example because trees are planar (Theorem \ref{planarbor}). The construction of~$T'$
itself adds only a~constant overhead to every step of the algorithm. As~$T'$ has~$m(T)=n(T)-1$
leaves and it is a~complete branching tree, it has at most~$m(T)$ internal vertices,
so~$n(T')\le 2n(T)$ as promised.

For each query path $T[x,y]$ we find the lower common ancestor of~$x$ and~$y$
using Theorem \ref{lcathm} and replace the path by the two half-paths. This
produces a~set~$Q'$ of at most~$2\vert Q\vert$ paths. If we remember the origin
of each of the new paths, the reconstruction of answers to the original queries
is then trivial.
\qed


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

\section{Special cases and related problems}

Finally, we will focus our attention on various special cases of the minimum
spanning tree problem which frequently arise in practice.

\examplen{Graphs with sorted edges}
When the edges 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 however can do better: As the minimality of a~spanning tree depends only on the
order of weights and not on the actual values (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.

\examplen{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.

\examplen{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. (More advanced tricks of this type have been
employed by Thorup in \cite{thorup:floatint} to extend his linear-time algorithm
for single-source shortest paths to FP edge lengths.)

\examplen{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)$. As it replaces a high-degree
vertex by vertices of degree~3, 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

\examplen{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 in~\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}.

\examplen{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 notes} is a~tree~$T\subseteq G$ which contains all the mandatory
vertices and its weight is minimum possible.

For $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 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}.

\examplen{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 an~almost matching 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 a~$\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.)

\endpart