The problem of finding a minimum spanning tree of a weighted graph is one of the
best studied problems in the area of combinatorial optimization since its birth.
Its colorful history (see \cite{graham:msthistory} and \cite{nesetril:history} for the full account)
-begins in~1926 with the pioneering work of Bor\accent23uvka
+begins in~1926 with the pioneering work of Bor\o{u}vka
\cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
who studied primarily an Euclidean version of the problem related to planning
of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
\proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
find its minimum spanning tree, defined as follows:
-\defn\thmid{mstdef}%
+\defn\id{mstdef}%
For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
\itemize\ibull
\:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
-\:A~\df{spanning tree} of $G$ is any its spanning subgraph which is a tree.
+\: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.
a union of (minimum) spanning trees of its connected components.
\endlist
-Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
+Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
mostly geometric setting, giving another efficient algorithm. However, when
computer science and graph theory started forming in the 1950's and the
spanning tree problem was one of the central topics of the flourishing new
disciplines, the previous work was not well known and the algorithms had to be
rediscovered several times.
-Recently, several significantly faster algorithms were discovered, most notably the
-$\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
-algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
-and Pettie \cite{pettie:ackermann}.
+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.}
+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.
-This chapter attempts to survery the important algorithms for finding the MST and it
-also presents several new ones.
+%--------------------------------------------------------------------------------
-\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.
definition of the MST. We can formulate an equivalent characterization using
an ordering of edges instead.
-\defnn{Heavy and light edges}\thmid{heavy}%
+\defnn{Heavy and light edges}\id{heavy}%
Let~$T$ be a~spanning tree. Then:
\itemize\ibull
\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
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}\thmid{lightlemma}%
+\lemman{Light edges}\id{lightlemma}%
Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
is not minimum.
= w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum.
\qed
-\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}}
+\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\ref{lightlemma}}
The converse of this lemma is also true and to prove it, we will once again use
technique of transforming trees by \df{exchanges} of edges. In the proof of the
a spanning tree. In fact, it is possible to transform any spanning tree
to any other spanning tree by a sequence of exchanges.
-\lemman{Exchange property for trees}\thmid{xchglemma}%
+\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'$.
hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
\qed
-\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}}
+\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\ref{xchglemma}}
-\lemman{Monotone exchanges}\thmid{monoxchg}%
+\lemman{Monotone exchanges}\id{monoxchg}%
Let $T$ be a spanning tree such that there are no $T$-light edges and $T'$
be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
transforming $T$ to~$T'$ such that the weight does not increase in any step.
than~$e'$ as $e'$ was not $T$-light.
\qed
-\theorem\thmid{mstthm}%
+\thmn{Minimality by order}\id{mstthm}%
A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
\proof
-If~$T$ is minimum, then by Lemma~\thmref{lightlemma} there are no $T$-light
+If~$T$ is minimum, then by Lemma~\ref{lightlemma} there are no $T$-light
edges.
Conversely, when $T$ is a spanning tree without $T$-light edges
and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone
-exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
+exchange lemma (\ref{monoxchg}) there exists a non-decreasing sequence
of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
and thus $T$~is also minimum.
\qed
However, as the following theorem shows, this is possible only if the weight
function is not injective.
-\theoremn{MST uniqueness}
+\thmn{MST uniqueness}%
If all edge weights are distinct, then the minimum spanning tree is unique.
\proof
Consider two minimum spanning trees $T_1$ and~$T_2$. According to the previous
theorem, there are no light edges with respect to neither of them, so by the
-Monotone exchange lemma (\thmref{monoxchg}) there exists a sequence of non-decreasing
+Monotone exchange lemma (\ref{monoxchg}) there exists a sequence of non-decreasing
edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
these edge exchanges must be in fact strictly increasing. On the other hand,
we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
$T_1$ and $T_2$ must be identical.
\qed
-\rem\thmid{edgeoracle}%
+\rem\id{edgeoracle}%
To simplify the description of MST algorithms, we will expect that the weights
of all edges are distinct and that instead of numeric weights (usually accompanied
by problems with representation of real numbers in algorithms) we will be given
original graph. In the few cases where we need a more concrete input, we will
explicitly state so.
-\section{The Red-Blue Meta-Algorithm}
+\nota\id{mstnota}%
+When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
+its unique minimum spanning tree.
+
+Another useful consequence is that whenever two graphs are isomorphic and the
+isomorphism preserves weight order, the isomorphism applies to their MST's
+as well:
+
+\defn
+A~\df{monotone isomorphism} of two weighted graphs $G_1=(V_1,E_1,w_1)$ and
+$G_2=(V_2,E_2,w_2)$ is a bijection $\pi: V_1\rightarrow V_2$ such that
+for each $u,v\in V_1: uv\in E_1 \Leftrightarrow \pi(u)\pi(v)\in E_2$ and
+for each $e,f\in E_1: w_1(e)<w_1(f) \Leftrightarrow w_2(\pi[e]) < w_2(\pi[f])$.
+
+\lemman{MST of isomorphic graphs}\id{mstiso}%
+Let~$G_1$ and $G_2$ be two weighted graphs with unique edge weights and $\pi$
+their monotone isomorphism. Then $\mst(G_2) = \pi[\mst(G_1)]$.
+
+\proof
+The isomorphism~$\pi$ maps spanning trees onto spanning trees and it preserves
+the relation of covering. Since it is monotone, it preserves the property of
+being a light edge (an~edge $e\in E(G_1)$ is $T$-light $\Leftrightarrow$
+the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by Theorem~\ref{mstthm}, $T$
+is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
+\qed
+
+%--------------------------------------------------------------------------------
+
+\section{The Red-Blue meta-algorithm}
Most MST algorithms can be described as special cases of the following procedure
(again following \cite{tarjan:dsna}):
-\algn{Red-Blue Meta-Algorithm}
+\algn{Red-Blue Meta-Algorithm}\id{rbma}%
\algo
-\algin A~graph $G$ with an edge comparison oracle (see \thmref{edgeoracle})
+\algin A~graph $G$ with an edge comparison oracle (see \ref{edgeoracle})
\:In the beginning, all edges are colored black.
\:Apply rules as long as possible:
\::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
-\::Or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \hphantas{red.}{blue.} \cmt{Red rule}
+\::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
that each of the classical MST algorithms can be described as a specific way
of choosing the rules in this procedure, which justifies the name meta-algorithm.
-\proclaim{Notation}%
+\nota
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
-Again by contradiction. Assume that $e$ is an edge painted red as the heaviest edge
+Again by contradiction. Suppose that $e$ is an edge painted red as the heaviest edge
of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
\figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
-\lemman{Black lemma}
+\lemman{Black lemma}%
As long as there exists a black edge, at least one rule can be applied.
\proof
reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest
edge on this cycle. This holds because all blue edges have been already proven
-to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\thmref{mstthm}).
+to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\ref{mstthm}).
In this case we can apply the red rule.
On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
\figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
-\theoremn{Red-Blue correctness}
+\thmn{Red-Blue correctness}%
For any selection of rules, the Red-Blue procedure stops and the blue edges form
the minimum spanning tree of the input graph.
\proof
To prove that the procedure stops, let us notice that no edge is ever recolored,
-so we must run out of black edges after at most $m$ steps. Recoloring
+so we must run out of black edges after at most~$m$ steps. Recoloring
to the same color is avoided by the conditions built in the rules, recoloring to
a different color would mean that the an edge would be both inside and outside~$T_{min}$
due to our Red and Blue lemmata.
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}\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.
+\:$T\=$ a forest consisting of vertices of~$G$ and no edges.
+\:While $T$ is not connected:
+\::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
+ separating $T_i$ from the rest of~$T$.
+\::Add all $e_i$'s to~$T$.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\lemma\id{boruvkadrop}%
+In each iteration of the algorithm, the number of trees in~$T$ drops at least twice.
+
+\proof
+Each tree gets merged with at least one of its neighbors, so each of the new trees
+contains two or more original trees.
+\qed
+
+\cor
+The algorithm stops in $\O(\log n)$ iterations.
+
+\lemma
+Bor\o{u}vka's algorithm outputs the MST of the input graph.
+
+\proof
+In every iteration of the algorithm, $T$ is a blue subgraph,
+because every addition of some edge~$e_i$ to~$T$ is a straightforward
+application of the Blue rule. We stop when the blue subgraph is connected, so
+we do not need the Red rule to explicitly exclude edges.
+
+It remains to show that adding the edges simultaneously does not
+produce a cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
+loss of generality we can assume that $C=T_1[u_1v_1]\,v_1u_2\,T_2[u_2v_2]\,v_2u_3\,T_3[u_3v_3]\, \ldots \,T_k[u_kv_k]\,v_ku_1$.
+Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
+or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation
+of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and we can continue in the same way,
+getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction.
+(Note that distinctness of edge weights was crucial here.)
+\qed
+
+\lemma\id{boruvkaiter}%
+Each iteration can be carried out in time $\O(m)$.
+
+\proof
+We assign a label to each tree and we keep a mapping from vertices to the
+labels of the trees they belong to. We scan all edges, map their endpoints
+to the particular trees and for each tree we maintain the lightest incident edge
+so far encountered. Instead of merging the trees one by one (which would be too
+slow), we build an auxilliary graph whose vertices are the labels of the original
+trees and edges correspond to the chosen lightest inter-tree edges. We find connected
+components of this graph, these determine how are the original labels translated
+to the new labels.
+\qed
+
+\thm
+Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
+
+\proof
+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.
+\:$T\=$ a single-vertex tree containing an~arbitrary vertex of~$G$.
+\:While there are vertices outside $T$:
+\::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
+\::$T\=T+uv$.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\lemma
+Jarn\'\i{}k's algorithm computers the MST of the input graph.
+
+\proof
+If~$G$ is connected, the algorithm always stops. Let us prove that in every step of
+the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying
+the Blue rule to the cut $\delta(T)$ separating~$T$ from the rest of the given graph. We need not care about
+the remaining edges, since for a connected graph the algorithm always stops with the right
+number of blue edges.
+\qed
+
+\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 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.
+From this, we can conclude:
+
+\thm
+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{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}}
+\algo
+\algin A~graph~$G$ with an edge comparison oracle.
+\: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$.
+\::Otherwise drop~$e$.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\lemma
+Kruskal's algorithm returns the MST of the input graph.
+
+\proof
+In every step, $T$ is a forest of blue trees. Adding~$e$ to~$T$
+in step~4 applies the Blue rule on the cut separating some pair of components of~$T$ ($e$ is the lightest,
+because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds
+to the Red rule on the cycle found ($e$~must be the heaviest, since all other edges of the
+cycle have been already processed). At the end of the algorithm, all edges are colored,
+so~$T$ must be the~MST.
+\qed
+
+\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
+for maintaining connected components, which supports queries and edge insertion.
+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.
+
+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
+See \cite{tarjan:setunion}.
+\qed
+
+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 \<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 relabel the smaller of the two components.
+
+We will study dynamic maintenance of connected components in more detail in Chapter~\ref{dynchap}.
+
+%--------------------------------------------------------------------------------
+
+\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
+a forest of trees, we can keep each tree contracted to a single vertex.
+This replaces the relatively complex tree-edge incidencies by simple
+vertex-edge incidencies, potentially speeding up the calculation at the
+expense of having to perform the contractions.
+
+We will show a contractive version of the Bor\o{u}vka's algorithm
+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 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.)
+
+We only need to be able to map edges of the contracted graph to the original
+edges, so each edge will carry a unique label $\ell(e)$ that will be preserved by
+contractions.
+
+\lemman{Flattening a multigraph}\id{flattening}%
+Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been
+removed and each bundle of parallel edges replaced by its lightest edge.
+Then $G'$~has the same MST as~$G$.
+
+\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'$
+for~$e$ makes~$T$ lighter. \qed
+
+\rem Removal of the heavier of a pair of parallel edges can be also viewed
+as an application of the Red rule on a two-edge cycle. And indeed it is, the
+Red-Blue procedure works on multigraphs as well as on simple graphs and all the
+classical algorithms also do. We would only have to be more careful in the
+formulations and proofs, which we preferred to avoid.
+
+\algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor}
+\algo
+\algin A~graph~$G$ with an edge comparison oracle.
+\:$T\=\emptyset$.
+\:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
+\:While $n(G)>1$:
+\::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}%
+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_k$, find
+connected components of this graph and renumber vertices in each component to
+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_i$~buckets, so it takes
+$\O(n_i+m_i)=\O(m_i)$.
+\qed
+
+\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)$.
+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{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 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$.
+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. 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
+To achieve the linear time complexity, the algorithm needs a very careful implementation,
+but we defer the technical details to section~\ref{bucketsort}.
+
+\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:
+
+\lemman{Contraction of MST edges}\id{contlemma}%
+Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
+produced by contracting $G$ along~$e$, and $\pi$ the bijection between edges of~$G-e$ and
+their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$
+
+\proof
+% We seem not to need this lemma for multigraphs...
+%If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the
+%Flattening lemma (\ref{flattening}), the MST stays the same and if we remove a parallel edge
+%or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates
+%in a MST.
+The right-hand side of the equality is a spanning tree of~$G$, let us denote it by~$T$ and
+the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$
+(by Theorem \ref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$,
+then $\pi[T[f]]$ is a path covered by~$\pi(f)$ in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path.
+In both cases, $f$ is $T'$-light, which contradicts the minimality of~$T'$. (We do not have
+a~multigraph version of the theorem, but the side we need is a~straightforward edge exchange,
+which obviously works in multigraphs as well.)
+\qed
+
+\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
+graphs are monotonely isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way.
+
+\defn
+A~\df{distractor of order~$k$,} denoted by~$D_k$, is a path on $n=2^k$~vertices $v_1,\ldots,v_n$
+where each edge $v_iv_{i+1}$ has its weight equal to the number of trailing zeroes in the binary
+representation of the number~$i$. The vertex $v_1$ is called a~\df{base} of the distractor.
+
+\rem
+Alternatively, we can use a recursive definition: $D_0$ is a single vertex, $D_{k+1}$ consists
+of two disjoint copies of~$D_k$ joined by an edge of weight~$k$.
+\figure{distractor.eps}{\epsfxsize}{A~distractor $D_3$ and its evolution (bold edges are contracted)}
-% mention Steiner trees
-% mention matroids
-% sorted weights
+\lemma
+A~single iteration of the contractive algorithm reduces~$D_k$ to a graph isomorphic with~$D_{k-1}$.
+
+\proof
+Each vertex~$v$ of~$D_k$ is incident with a single edge of weight~1. The algorithm therefore
+selects all weight~1 edges and contracts them. This produces a graph which is
+exactly $D_{k-1}$ with all weights increased by~1, which does not change the relative order of edges.
+\qed
+
+\defn
+A~\df{hedgehog}~$H_{a,k}$ is a graph consisting of $a$~distractors $D_k^1,\ldots,D_k^a$ of order~$k$
+together with edges of a complete graph on the bases of the distractors. These additional edges
+have arbitrary weights, but heavier than the edges of all distractors.
+
+\figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)}
+
+\lemma
+A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a graph isomorphic with $H_{a,k-1}$.
+
+\proof
+Each vertex is incident with an edge of some distractor, so the algorithm does not select
+any edge of the complete graph. Contraction therefore reduces each distractor to a smaller
+distractor (modulo an additive factor in weight) and leaves the complete graph intact.
+This is monotonely isomorphic to $H_{a,k-1}$.
+\qed
+
+\thmn{Lower bound for Contractive Bor\o{u}vka}%
+For each $n$ there exists a graph on $\Theta(n)$ vertices and $\Theta(n)$ edges
+such that the Contractive Bor\o{u}vka's algorithm spends time $\Omega(n\log n)$ on it.
+
+\proof
+Consider the hedgehog $H_{a,k}$ for $a=\lceil\sqrt n\rceil$ and $k=\lceil\log_2 a\rceil$.
+It has $a\cdot 2^k = \Theta(n)$ vertices and ${a \choose 2} + a\cdot 2^k = \Theta(a^2) + \Theta(a^2) = \Theta(n)$ edges
+as we wanted.
+
+By the previous lemma, the algorithm proceeds through a sequence of hedgehogs $H_{a,k},
+H_{a,k-1}, \ldots, H_{a,0}$ (up to monotone isomorphism), so it needs a logarithmic number of iterations plus some more
+to finish on the remaining complete graph. Each iteration runs on a graph with $\Omega(n)$
+edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
+\qed
+
+\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.
+
+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