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.
+\:A~\df{spanning tree} of $G$ is any its spanning subgraph that 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.
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\timesbeta(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}.
+In the next 50 years, several significantly faster algorithms were discovered, ranging
+from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
+over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
+and Pettie \cite{pettie:ackermann}, to another algorithm by Pettie \cite{pettie:optimal}
+whose time complexity is provably optimal.
-\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.
+In the upcoming chapters, we will explore this colorful universe of MST algorithms.
+We will meet the standard works of the classics, the clever ideas of their successors,
+various approaches to the problem including randomization and solving of important
+special cases.
%--------------------------------------------------------------------------------
-\section{Basic Properties}
+\section{Basic properties}\id{mstbasics}%
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
+For the whole section, we will fix a~connected 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.
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.
+\:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge.
\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.
+Edges of the tree~$T$ itself are neither heavy nor light. We will sometimes
+use the name \df{non-heavy} for edges which are either light or contained
+in the tree.
\lemman{Light edges}\id{lightlemma}%
Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
\lemman{Exchange property for trees}\id{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,
+a sequence of edge exchanges that 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'$.
%--------------------------------------------------------------------------------
-\section{The Red-Blue Meta-Algorithm}
+\section{The Red-Blue meta-algorithm}
Most MST algorithms can be described as special cases of the following procedure
(again following \cite{tarjan:dsna}):
\: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}
+\::or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \rack{blue.}{red.\hfil} \cmt{Red rule}
\algout Minimum spanning tree of~$G$ consisting of edges colored blue.
\endalgo
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}%
+\lemman{Blue lemma}\id{bluelemma}%
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
+If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ that 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}%
+\lemman{Red lemma}\id{redlemma}%
When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
\proof
lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
\qed
+\para
+The Red lemma actually works in both directions and it can be used to characterize
+all non-MST edges, which will turn out to be useful in the latter chapters.
+
+\corn{Cycle rule}\id{cyclerule}%
+An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.
+
+\proof
+The implication from the right to the left is the Red lemma. In the other
+direction, when~$e$ is not contained in~$T_{min}$, it is $T_{min}$-heavy (by
+Theorem \ref{mstthm}), so it is the heaviest edge on the cycle $T_{min}[e]+e$.
+\qed
+
+\rem
+The MST problem is a~special case of the problem of finding the minimum basis
+of a~weighted matroid. Surprisingly, when we modify the Red-Blue procedure to
+use the standard definitions of cycles and cuts in matroids, it will always
+find the minimum basis. Some of the other MST algorithms also easily generalize to
+matroids and in some sense matroids are exactly the objects where ``the greedy approach works''. We
+will however not pursue this direction in our work, referring the reader to the Oxley's monograph
+\cite{oxley:matroids} instead.
+
%--------------------------------------------------------------------------------
-\section{Classical algorithms}
+\section{Classical algorithms}\id{classalg}%
The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.
For each of them, we first show the general version of the algorithm, then we prove that
it gives the correct result and finally we discuss the time complexity of various
implementations.
+\paran{Bor\o{u}vka's algorithm}%
+The oldest MST algorithm is based on a~simple idea: grow a~forest in a~sequence of
+iterations until it becomes connected. We start with a~forest of isolated
+vertices. In each iteration, we let each tree of the forest select the lightest
+edge of those having exactly one endpoint in the tree (we will call such edges
+the \df{neighboring edges} of the tree). We add all such edges to the forest and
+pAroceed with the next iteration.
+
\algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
Follows from the previous lemmata.
\qed
+\paran{Jarn\'\i{}k's algorithm}%
+The next algorithm, discovered independently by Jarn\'\i{}k, Prim and Dijkstra, is similar
+to Bor\o{u}vka's algorithm, but instead of the whole forest it concentrates on
+a~single tree. It starts with a~single vertex and it repeatedly extends the tree
+by the lightest neighboring edge until it spans the whole graph.
+
\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}%
\algo
\algin A~graph~$G$ with an edge comparison oracle.
number of blue edges.
\qed
-\impl
-The most important part of the algorithm is finding \em{neighboring edges,} i.e., edges
-of the cut $\delta(T)$. In a~straightforward implementation,
-searching for the lightest neighboring edge takes $\Theta(m)$ time, so the whole
-algorithm runs in time $\Theta(mn)$.
+\impl\id{jarnimpl}%
+The most important part of the algorithm is finding \em{neighboring edges.}
+In a~straightforward implementation, searching for the lightest neighboring
+edge takes $\Theta(m)$ time, so the whole algorithm runs in time $\Theta(mn)$.
We can do much better by using a binary
heap to hold all neighboring edges. In each iteration, we find and delete the
minimum edge from the heap and once we expand the tree, we insert the newly discovered
-neighboring edges to the heap while deleting the neighboring edges which become
+neighboring edges to the heap while deleting the neighboring edges that become
internal to the new tree. Since there are always at most~$m$ edges in the heap,
each heap operation takes $\O(\log m)=\O(\log n)$ time. For every edge, we perform
at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time in total.
Jarn\'\i{}k's algorithm finds the MST of a~given graph in time $\O(m\log n)$.
\rem
-We will show several faster implementations in section \ref{fibonacci}.
+We will show several faster implementations in section \ref{iteralg}.
+
+\paran{Kruskal's algorithm}%
+The last of the three classical algorithms processes the edges of the
+graph~$G$ greedily. It starts with an~empty forest and it takes the edges of~$G$
+in order of their increasing weights. For every edge, it checks whether its
+addition to the forest produces a~cycle and if it does not, the edge is added.
+Otherwise, the edge is dropped and not considered again.
-\algn{Kruskal \cite{kruskal:mst}, the Greedy algorithm}
+\algn{Kruskal \cite{kruskal:mst}}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
-\:Sort edges of~$G$ by their increasing weight.
+\:Sort edges of~$G$ by their increasing weights.
\:$T\=\emptyset$. \cmt{an empty spanning subgraph}
\:For all edges $e$ in their sorted order:
\::If $T+e$ is acyclic, add~$e$ to~$T$.
\impl
Except for the initial sorting, which in general takes $\Theta(m\log m)$ time, the only
-other non-trivial operation is the detection of cycles. What we need is a data structure
+other non-trivial operation is the detection of cycles. What we need is a~data structure
for maintaining connected components, which supports queries and edge insertion.
-(This is also known under the name Disjoint Set Union problem, i.e., maintenance
-of an~equivalence relation on a~set with queries on whether two elements are equivalent
-and the operation of joining two equivalence classes into one.)
-The following theorem shows that it can be done with surprising efficiency.
+This is closely related to the well-known Disjoint Set Union problem:
+
+\problemn{Disjoint Set Union (DSU)}
+Maintain an~equivalence relation on a~finite set under a~sequence of operations \<Union>
+and \<Find>. The \<Find> operation tests whether two elements are equivalent and \<Union>
+joins two different equivalence classes into one.
+
+\para
+We can maintain the connected components of our forest~$T$ as equivalence classes. When we want
+to add an~edge~$uv$, we first call $\<Find>(u,v)$ to check if both endpoints of the edge lie in
+the same components. If they do not, addition of this edge connects both components into one,
+so we perform $\<Union>(u,v)$ to merge the equivalence classes.
-\thmn{Incremental connectivity}%
-When only edge insertions and connectivity queries are allowed, connected components
-can be maintained in $\O(\alpha(n))$ time amortized per operation.
+Tarjan and van Leeuwen have shown that there is a~data structure for the DSU problem
+with surprising efficiency:
+
+\thmn{Disjoint Set Union, Tarjan and van Leeuwen \cite{tarjan:setunion}}\id{dfu}%
+Starting with a~trivial equivalence with single-element classes, a~sequence of operations
+comprising of $n$~\<Union>s intermixed with $m\ge n$~\<Find>s can be processed in time
+$\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's function
+(see Definition \ref{ackerinv}).
\proof
-Proven by Tarjan and van Leeuwen in \cite{tarjan:setunion}.
+See \cite{tarjan:setunion}.
\qed
-\FIXME{Define Ackermann's function. Use $\alpha(m,n)$?}
+This completes the following theorem:
+
+\thm\id{kruskal}%
+Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
+If the edges are already sorted by their weights, the time drops to
+$\O(m\timesalpha(m,n))$.
+
+\proof
+We spend $\O(m\log n)$ on sorting, $\O(m\timesalpha(m,n))$ on processing the sequence
+of \<Union>s and \<Find>s, and $\O(m)$ on all other work.
+\qed
\rem
-The cost of the operations on components is of course dwarfed by the complexity
+The cost of the \<Union> and \<Find> operations is of course dwarfed by the complexity
of sorting, so a much simpler (at least in terms of its analysis) data
structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
per operation. For example, we can label vertices with identifiers of the
-corresponding components and always recolor the smaller of the two components.
+corresponding components and always relabel the smaller of the two components.
-\thm
-Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$
-or $\O(m\timesalpha(n))$ if the edges are already sorted by their weights.
-
-\proof
-Follows from the above analysis.
-\qed
+We will study dynamic maintenance of connected components in more detail in Chapter~\ref{dynchap}.
%--------------------------------------------------------------------------------
-\section{Contractive algorithms}
+\section{Contractive algorithms}\id{contalg}%
While the classical algorithms are based on growing suitable trees, they
can be also reformulated in terms of edge contraction. Instead of keeping
in which these costs are carefully balanced, leading for example to
a linear-time algorithm for MST in planar graphs.
-There are two definitions of edge contraction which differ when an edge of a
-triangle is contracted. Either we unify the other two edges to a single edge
+There are two definitions of edge contraction that differ when an edge of
+a~triangle is contracted. Either we unify the other two edges to a single edge
or we keep them as two parallel edges, leaving us with a~multigraph. We will
use the multigraph version and we will show that we can easily reduce the multigraph
to a simple graph later. (See \ref{contract} for the exact definitions.)
\proof
Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction:
Loops can be never contained in a spanning tree. If there is a spanning tree~$T$
-containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
+containing a~removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
for~$e$ makes~$T$ lighter. \qed
\rem Removal of the heavier of a pair of parallel edges can be also viewed
\:$T\=\emptyset$.
\:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
\:While $n(G)>1$:
-\::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$.
-\::$T\=T\cup \{ \ell(e_i) \}$. \cmt{Remember labels of all selected edges.}
-\::Contract $G$ along all edges $e_i$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
+\::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$.
+\::$T\=T\cup \{ \ell(e_k) \}$. \cmt{Remember labels of all selected edges.}
+\::Contract $G$ along all edges $e_k$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
\::Flatten $G$, removing parallel edges and loops.
\algout Minimum spanning tree~$T$.
\endalgo
+\nota
+For the analysis of the algorithm, we will denote the graph considered by the algorithm
+at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and the number
+of vertices and edges of this graph by $n_i$ and $m_i$ respectively.
+
\lemma\id{contiter}%
-Each iteration of the algorithm can be carried out in time~$\O(m)$.
+The $i$-th iteration of the algorithm (also called the \df{Bor\o{u}vka step}) can be carried
+out in time~$\O(m_i)$.
\proof
The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly
to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}):
-We build an auxillary graph containing only the selected edges~$e_i$, find
+We build an auxillary graph containing only the selected edges~$e_k$, find
connected components of this graph and renumber vertices in each component to
-the identifier of the component. This takes $\O(m)$ time.
+the identifier of the component. This takes $\O(m_i)$ time.
Flattening is performed by first removing the loops and then bucket-sorting the edges
(as ordered pairs of vertex identifiers) lexicographically, which brings parallel
-edges together. The bucket sort uses two passes with $n$~buckets, so it takes
-$\O(n+m)=\O(m)$.
+edges together. The bucket sort uses two passes with $n_i$~buckets, so it takes
+$\O(n_i+m_i)=\O(m_i)$.
\qed
-\thm
-The Contractive Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
+\thm\id{contborthm}%
+The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
+time $\O(\min(n^2,m\log n))$.
\proof
As in the original Bor\o{u}vka's algorithm, the number of iterations is $\O(\log n)$.
-Then apply the previous lemma.
+When combined with the previous lemma, it gives an~$\O(m\log n)$ upper bound.
+
+To get the $\O(n^2)$ bound, we observe that the number of trees in the non-contracting
+version of the algorithm drops at least by a factor of two in each iteration (Lemma \ref{boruvkadrop})
+and the same must hold for the number of vertices in the contracting version.
+Therefore $n_i\le n/2^i$. While the number of edges need not decrease geometrically,
+we still have $m_i\le n_i^2$ as the graphs~$G_i$ are simple (we explicitly removed multiple
+edges and loops at the end of the previous iteration). Hence the total time spent
+in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$.
\qed
-\thmn{\cite{mm:mst}}\id{planarbor}%
+\thmn{Contractive Bor\o{u}vka on planar graphs, \cite{mm:mst}}\id{planarbor}%
When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
time $\O(n)$.
\proof
-Let us denote the graph considered by the algorithm at the beginning of the $i$-th
-iteration by $G_i$ (starting with $G_0=G$) and its number of vertices and edges
-by $n_i$ and $m_i$ respectively. As we already know from the previous lemma,
-the $i$-th iteration takes $\O(m_i)$ time. We are going to prove that the
-$m_i$'s are decreasing geometrically.
-
-The number of trees in the non-contracting version of the algorithm drops
-at least by a factor of two in each iteration (Lemma \ref{boruvkadrop}) and the
-same must hold for the number of vertices in the contracting version.
-Therefore $n_i\le n/2^i$.
-
-However, every $G_i$ is planar, because the class of planar graphs is closed
-under edge deletion and contraction. The~$G_i$ is also simple as we explicitly removed multiple edges and
-loops at the end of the previous iteration. Hence we can use the standard theorem on
+Let us refine the previous proof. We already know that $n_i \le n/2^i$. We will
+prove that when~$G$ is planar, the $m_i$'s are decreasing geometrically. We know that every
+$G_i$ is planar, because the class of planar graphs is closed under edge deletion and
+contraction. Moreover, $G_i$~is also simple, so we can use the standard theorem on
the number of edges of planar simple graphs (see for example \cite{diestel:gt}) to get $m_i\le 3n_i \le 3n/2^i$.
-From this we get that the total time complexity is $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$.
+The total time complexity of the algorithm is therefore $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$.
\qed
\rem
There are several other possibilities how to find the MST of a planar graph in linear time.
For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously
-working on the graph and its topological dual. We will show one more linear algorithm soon. The advantage
-of our approach is that we do not need to construct the planar embedding explicitly.
-
-\rem
-To achieve the linear time complexity, the algorithm needs a very careful implementation.
-Specifically, when we represent the graph using adjacency lists, whose heads are stored
-in an array indexed by vertex identifiers, we must renumber the vertices in each iteration.
-Otherwise, unused elements could end up taking most of the space in the arrays and the scans of these
-arrays would have super-linear cost with respect to the size of the current graph~$G_i$.
+working on the graph and its topological dual. The advantage of our approach is that we do not need
+to construct the planar embedding explicitly. We will show one more linear algorithm
+in section~\ref{minorclosed}.
\rem
-The algorithm can be also implemented on the pointer machine. Representation of graphs
-by pointer structures easily avoids the aforementioned problems with sparse arrays,
-but we need to handle the bucket sorting somehow. We can create a small data structure
-for every vertex and use a pointer to this structure as a unique identifier of the vertex.
-We will also keep a list of all vertex structures. During the bucket sort, each vertex
-structure will contain a pointer to the corresponding bucket and the vertex list will
-define the order of vertices (which can be arbitrary).
+To achieve the linear time complexity, the algorithm needs a very careful implementation,
+but we defer the technical details to section~\ref{bucketsort}.
-\para
+\paran{General contractions}%
Graph contractions are indeed a~very powerful tool and they can be used in other MST
algorithms as well. The following lemma shows the gist:
\rem
In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$.
+\paran{A~lower bound}%
Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity
is tight. The graphs do not have unique weights, but they are constructed in a way that
the algorithm never compares two edges with the same weight. Therefore, when two such
edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
\qed
-%--------------------------------------------------------------------------------
-
-\section{Minor-closed graph classes}
-
-The contracting algorithm given in the previous section 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
-A~graph~$H$ is a \df{minor} of a~graph~$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 planar graphs and more generally graphs
-embeddable in any fixed surface. Many nice properties of planar graphs extend
-to these classes, too, most notably the linearity of the number of edges.
-
-\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{Density of minor-closed classes}
-A~minor-closed class of graphs has finite edge density if and only if it is
-a non-trivial class.
-
-\proof
-See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions.
-\qed
-
-\thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}%
-For any fixed non-trivial minor-closed class~$\cal C$ of graphs, Algorithm \ref{contbor} finds
-the MST of any graph in 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 least $n_i/2$ edges get selected in the $i$-th iteration.
-Hence at least a half of the vertices participates in contractions, so
-$n_i\le 3/4\cdot n_{i-1}$. 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}}
-
-%--------------------------------------------------------------------------------
-
-\section{Using Fibonacci heaps}
-\id{fibonacci}
-
-We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\O(m\log n)$ time
-(and this bound can be easily shown to be tight). 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 neighboring
-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 keep the lightest edge~$uv$ such that $u$~lies
-in~$T$. We will call these edges \df{active edges} and keep them in a~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 a 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{Jarn\'\i{}k with active edges; 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~heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(vw)$, initially empty.
-\:$A\=$ an~auxiliary array mapping 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
-
-\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 maximum 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 a~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 and there are at most $n$ elements in the heap at any given time,
-so 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.
+\remn{Disconnected graphs}\id{disconn}%
+The basic properties of minimum spanning trees and the algorithms presented in
+this chapter apply to minimum spanning forests of disconnected graphs, too.
+The proofs of our theorems and the steps of our algorithms are based on adjacency
+of vertices and existence of paths, so they are always local to a~single
+connected component. The Bor\o{u}vka's and Kruskal's algorithm need no changes,
+the Jarn\'\i{}k's algorithm has to be invoked separately for each component.
-\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 run in~$\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$, giving $\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 worst case, but it does not matter here) and their
-authors claim implementation advantages.
-
-\FIXME{Mention Thorup's Fibonacci-like heaps for integers?}
-
-\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 above version of 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 Jarn\'\i{}k's algorithm with active edges (\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
-improved Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while.
-The good choice of the stopping condition is to place a~limit on the size of the heap.
-Start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
-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^{2m_0/n}$. \cmt{the limit on heap size}
-\::While there is a~vertex $v_0\not\in F$:
-\:::Run the improved 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 had 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. The trees from which
-$F_i$~has been constructed will 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 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 the vertices of every
-such 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 elements stored in the heap correspond
- to some of the edges incident with vertices of~$R_i^j$, the condition~(*) is fulfilled;
-\: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{%
- To make this true, we counted the edges incident with the \em{vertices} of the tree
- instead of edges incident with the tree itself, because we needed the tree edges
- to be counted 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 < 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 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^{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\vdots^{\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
-
-\rem
-Gabow et al.~\cite{gabow:mst} have shown how to speed this algorithm up 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.}
-
-\FIXME{Reference to Q-Heaps.}
-
-%--------------------------------------------------------------------------------
-
-\section{Verification of minimality}
-
-
-\section{What we ought to cite}
-
-Eisner's tutorial \cite{eisner:tutorial}
-
-\cite{pettie:onlineverify} online lower bound
-
-% use \para
-% G has to be connected, so m=O(n)
-% mention Steiner trees
-% mention matroids
-% sorted weights
-% \O(...) as a set?
-% impedance mismatch in terminology: contraction of G along e vs. contraction of e.
-% use \delta(X) notation
-% mention disconnected graphs
-% unify use of n(G) vs. n
-% Euclidean MST
-% Some algorithms (most notably Fredman-Tarjan) do not need flattening
-% more references to RAM
+We can also extend the notion of light and heavy edges with respect
+to a~tree to forests: When an~edge~$e$ connects two vertices lying in the same
+tree~$T$ of a~forest~$F$, it is $F$-heavy iff it is $T$-heavy (similarly
+for $F$-light). Edges connecting two different trees are always considered
+$F$-light. Again, a~spanning forest~$F$ is minimum iff there are no $F$-light
+edges.
\endpart
projects / saga.git / blobdiff