X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=mst.tex;h=5cccbb9810448adefd7980aa99b52adcebc11ac5;hb=f12a638dc99ba01efebc5534d722db651f4ac555;hp=58a8d5ff5952d5f727038735fb5ffe1deba0813b;hpb=6e1c4a014781bb45b7714508459412afece67d63;p=saga.git diff --git a/mst.tex b/mst.tex index 58a8d5f..5cccbb9 100644 --- a/mst.tex +++ b/mst.tex @@ -24,61 +24,66 @@ find its minimum spanning tree, defined as follows: 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 spanning subgraph of~$G$ 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~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$ - is the smallest possible of all the spanning trees of~$G$. + is the smallest possible among all the spanning trees of~$G$. \:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as a union of (minimum) spanning trees of its connected components. \endlist Bor\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 +mostly geometric setting. He has discovered 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 an~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 canonical works of the classics, the clever ideas of their successors, +various approaches to the problem including randomization and solving of important +special cases. At several places, we will try to contribute our little stones to this +mosaic. -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}. +several important theorems which will serve as a~foundation for our MST algorithms. +We will mostly 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. First of all, let us show that the weights on edges are not necessary for the definition of the MST. We can formulate an equivalent characterization using -an ordering of edges instead. +an~ordering of edges instead. \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$. +\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ with~$y$. \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and the edges of this path \df{edges covered by~$e$}. -\:An edge~$e$ is called \df{light with respect to~$T$} (or just \df{$T$-light}) if it covers a heavier edge, i.e., if there - is an edge $f\in T[e]$ such that $w(f) > w(e)$. -\:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light. +\: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 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$ cover only themselves and thus they are neither heavy nor light. +The same can happen if an~edge outside~$T$ covers only edges of the same weight, +but this will be rare because all edge weights will be usually distinct. \lemman{Light edges}\id{lightlemma}% Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$ @@ -86,7 +91,7 @@ is not minimum. \proof If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such -that $w(e')>w(e)$. Now $T-e'$ is a forest of two trees with endpoints of~$e$ +that $w(e')>w(e)$. Now $T-e'$ ($T$~with the edge~$e'$ removed) is a forest of two trees with endpoints of~$e$ located in different components, so adding $e$ to this forest must restore connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T') = w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum. @@ -95,34 +100,36 @@ connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T') \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 +the technique of transforming trees by \df{exchanges of edges.} In the proof of the lemma, we have made use of the fact that whenever we exchange an edge~$e$ of -a spanning tree for another edge~$f$ covered by~$e$, the result is again -a spanning tree. In fact, it is possible to transform any spanning tree +a~spanning tree for another edge~$f$ covered by~$e$, the result is again +a~spanning tree. In fact, it is possible to transform any spanning tree to any other spanning tree by a sequence of exchanges. \lemman{Exchange property for trees}\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'$. \proof By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, both trees are identical and no exchanges are needed. Otherwise, the trees are different, -but as they are of the same size, there must exist an edge $e'\in T'\setminus T$. +but as they have the same number of edges, there must exist an edge $e'\in T'\setminus T$. The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning -tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction +tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$. Now we can apply the induction hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence. \qed \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\ref{xchglemma}} +\>In some cases, a~much stronger statement is true: + \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. +transforming $T$ to~$T'$ such that the weight of the tree does not decrease in any step. \proof We improve the argument from the previous proof, refining the induction step. @@ -136,15 +143,17 @@ $T'\setminus T^*$, since these are the only edges considered by the induction steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$ by picking the lightest such edge. -Now consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not +Let us consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not $T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is -either equal to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$, -where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter one -$w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter +either identical to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$, +where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter we have +$w(f)\ge w(e')$ due to the choice of~$e'$ and all other edges on~$C$ are lighter than~$e'$ as $e'$ was not $T$-light. \qed -\thmn{Minimality by order}\id{mstthm}% +This lemma immediately implies that Lemma \ref{lightlemma} works in both directions: + +\thmn{Minimality of spanning trees}\id{mstthm}% A~spanning tree~$T$ is minimum iff there is no $T$-light edge. \proof @@ -158,12 +167,12 @@ and thus $T$~is also minimum. \qed In general, a single graph can have many minimum spanning trees (for example -a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$ +a complete graph on~$n$ vertices with unit edge weights has $n^{n-2}$ minimum spanning trees according to the Cayley's formula \cite{cayley:trees}). However, as the following theorem shows, this is possible only if the weight function is not injective. -\thmn{MST uniqueness}% +\thmn{Uniqueness of MST}% If all edge weights are distinct, then the minimum spanning tree is unique. \proof @@ -174,64 +183,87 @@ 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. +\looseness=1 %%HACK%% \qed -\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 -a comparison oracle, that is a function which answers questions ``$w(e)w(e_2)>\ldots>w(e_k)>w(e_1)$, -which is a contradiction. (Note that distinctness of edge weights was crucial here.) +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_2)>\ldots>w(e_k)>w(e_1)$, which is a~contradiction. +(Note that distinctness of edge weights was crucial here.) \qed -\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 neighboring trees, so each of the new trees -consists of at least two original trees. -\qed - -\cor -The algorithm stops in $\O(\log n)$ iterations. - \lemma\id{boruvkaiter}% Each iteration can be carried out in time $\O(m)$. \proof -Following \cite{mm:mst}, -we assign a label to each tree and we keep a mapping from vertices to the +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 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 the original labels are translated +slow), we build an auxiliary graph whose vertices are the labels of the original +trees and edges correspond to the chosen lightest inter-tree edges. We find the connected +components of this graph, and 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)$. +The Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$. \proof Follows from the previous lemmata. \qed -\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}} +\paran{Jarn\'\i{}k's algorithm}% +The next algorithm, discovered independently by Jarn\'\i{}k, Prim and Dijkstra, is similar +to the 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 the tree 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 any vertex of~$G$. +\:$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$. @@ -377,41 +453,48 @@ Follows from the previous lemmata. \endalgo \lemma -Jarn\'\i{}k's algorithm returns the MST of the input graph. +The Jarn\'\i{}k's algorithm computes the MST of the input graph. \proof -During the course of the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying -the Blue rule to a cut between~$T$ and the rest of the given graph. We need not care about +If~$G$ is connected, the algorithm always stops. In every step of +the algorithm, $T$ is always a blue tree. because 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 -The most important part of the algorithm is finding \em{neighboring edges,} i.e., edges -going between $T$ and $V(G)\setminus T$. In the 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 the \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 and delete the neighboring edges that became 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 the graph in time $\O(m\log n)$. +The Jarn\'\i{}k's algorithm computes 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. -\:$T\=\emptyset$. \cmt{an empty spanning subgraph} +\:Sort edges of~$G$ by their increasing weights. +\:$T\=\hbox{an empty spanning subgraph}$. \:For all edges $e$ in their sorted order: \::If $T+e$ is acyclic, add~$e$ to~$T$. \::Otherwise drop~$e$. @@ -419,53 +502,75 @@ We will show several faster implementations in section \ref{fibonacci}. \endalgo \lemma -Kruskal's algorithm returns the MST of the input graph. +The 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 two components of~$T$ ($e$ is the lightest, +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 have been colored, +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 n)$ time, the only -other non-trivial operation is detection of cycles. What we need is a data structure +Except for the initial sorting, which in general requires $\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. -The following theorem shows that it can be done with a 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 \ +and \. The \ operation tests whether two elements are equivalent and \ +joins two different equivalence classes into one. -\thmn{Incremental connectivity}% -When only edge insertions and queries are allowed, connected components -can be maintained in $\O(\alpha(n))$ time amortized per operation. +\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 $\(u,v)$ to check if both endpoints of the edge lie in +the same component. If they do not, addition of this edge connects both components into one, +so we perform $\(u,v)$ to merge the equivalence classes. + +Tarjan has shown that there is a~data structure for the DSU problem +of surprising efficiency: + +\thmn{Disjoint Set Union, Tarjan \cite{tarjan:setunion}}\id{dfu}% +Starting with a~trivial equivalence with single-element classes, a~sequence of operations +comprising of $n$~\s intermixed with $m\ge n$~\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}% +The 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)$ time on sorting, $\O(m\timesalpha(m,n))$ on processing the sequence +of \s and \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 \ and \ 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\alpha(n))$ if the edges are already sorted by their weights. +We will study dynamic maintenance of connected components in more detail in Chapter~\ref{dynchap}. -\proof -Follows from the above analysis. -\qed +%-------------------------------------------------------------------------------- -\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 -a forest of trees, we can keep each tree contracted to a single vertex. +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. @@ -474,33 +579,28 @@ 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 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 show that we can easily reduce the multigraph -to a simple graph later. (See \ref{contract} for the exact definitions.) +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)$ which will be preserved by +edges, so we let each edge 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. +Let $G$ be a multigraph and $G'$ its subgraph obtaining by removing loops +and replacing each bundle of parallel edges by its lightest edge. Then $G'$~has the same MST as~$G$. \proof -Loops can be never used 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$ in~$T$ makes it 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 only would have to be more careful in the -formulations and proofs, which we preferred to avoid. We also note that most of -the algorithms can be run on disconnected multigraphs with little or no -modifications. +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'$, exchanging $e'$ +for~$e$ makes~$T$ lighter. (This is indeed the multigraph version of the Red +lemma applied to a~two-edge cycle, as we will see in \ref{multimst}.) +\qed \algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor} \algo @@ -508,89 +608,86 @@ modifications. \:$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. -\::Flatten $G$, removing parallel edges and loops. +\::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$. +\::$T\=T\cup \{ \ell(e_1),\ldots,\ell(e_n) \}$.\hfil\break\cmt{Remember labels of all selected edges.} +\::Contract all edges $e_k$, inheriting labels and weights.\foot{In other words, we will ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.} +\::Flatten $G$ (remove 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. A~single iteration +of the algorithm will be called a~\df{Bor\o{u}vka step}. + \lemma\id{contiter}% -Each iteration of the algorithm can be carried out in time~$\O(m)$. +The $i$-th 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 +to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}): +We build an~auxiliary 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 phases is $\O(\log n)$. -Then apply the previous lemma. +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{\cite{mm:mst}}\id{planarbor}% +On planar graphs, the algorithm runs much faster: + +\thmn{Contractive Bor\o{u}vka on planar graphs}\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 exponentially. - -The number of trees in the non-contracting version of the algorithm decreases -at least twice 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. So 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 bound 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 other possibilities how to find the MST of a planar graph in linear time. -Matsui \cite{matsui:planar} has described an algorithm based on simultaneously -processing the graph and its dual. The advantage of our approach is that we do not -need to construct the planar embedding first. - -\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 identifiers could end up taking most of space in the arrays and scans of these -arrays would have super-linear cost with respect to the size of the current graph~$G_i$. +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 another simpler linear-time 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, but has to be fixed). +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.$$ +produced by contracting~$e$ in~$G$, 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... @@ -598,63 +695,66 @@ their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$ %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 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$ -(according to Theorem \ref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$, +(by the Minimality 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 this direction is a straightforward edge exchange, -which of course works in multigraphs as well.) +a~multigraph version of the theorem, but the direction we need is a~straightforward edge exchange, +which obviously works in multigraphs as well as in simple graphs.) \qed \rem -In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$. +In the Contractive Bor\o{u}vka's algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$. -Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity +\paran{A~lower bound}% +Finally, we will show a family of graphs for which 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. +graphs are monotonically 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$ +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$ consists -of two disjoint copies of $D_{k-1}$ joined by an edge of weight~$k$. - \figure{distractor.eps}{\epsfxsize}{A~distractor $D_3$ and its evolution (bold edges are contracted)} +\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$. + \lemma -A~single iteration of the contractive algorithm reduces~$D_k$ to a graph isomorphic with~$D_{k-1}$. +A~single iteration of the contractive algorithm reduces the distractor~$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. +selects all weight~1 edges and contracts them. This produces a~graph that is +equal to $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 unique weights larger than~$k$, i.e., they are heavier than the edges of the distractors. +together with edges of a complete graph on the bases of these distractors. The additional edges +have arbitrary weights that are heavier than the edges of all the 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}$. +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}$. +distractor (modulo an additive factor in weight) and it leaves the complete graph intact. +The resulting graph is monotonely isomorphic to $H_{a,k-1}$. \qed +When we set the parameters appropriately, we get the following lower bound: + \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(m\log n)$ on it. +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$. @@ -667,167 +767,55 @@ to finish on the remaining complete graph. Each iteration runs on a graph with $ 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 some 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 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 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$. +\section{Lifting restrictions} -\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 notable the linearity of the number of edges. +In order to have a~simple and neat theory, we have introduced several restrictions +on the graphs in which we search for the MST. As in some rare cases we are going to +meet graphs that do not fit into this simplified world, let us quickly examine what +happens when the restrictions are lifted. -\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$. +\paran{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. -\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 from 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})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 performed -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$. -\:$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\cup \{ \ell(e_i) \}$. -\::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 only.) - -\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 separating~$v$ from the rest of the graph (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 got $t=12$ from the -general version). 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$, -hence by the same argument as in the previous proof, for at least $n/2$ -vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$. -\qed - - - - -\section{Using Fibonacci heaps} -\id{fibonacci} +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. -% 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 +\paran{Multigraphs}\id{multimst}% +All theorems and algorithms from this chapter work for multigraphs as well, +only the notation sometimes gets crabbed, which we preferred to avoid. The Minimality +theorem and the Blue rule stay unchanged. The Red rule is naturally extended to +self-loops (which are never in the MST) and two-edge cycles (where the heavier +edge can be dropped) as already suggested in the Flattening lemma (\ref{flattening}). + +\paran{Multiple edges of the same weight}\id{multiweight}% +In case when the edge weights are not distinct, the characterization of minimum +spanning trees using light edges is still correct, but the MST is no longer unique +(as already mentioned, there can be as much as~$n^{n-2}$ MST's). + +In the Red-Blue procedure, we have to avoid being too zealous. The Blue lemma cannot +guarantee that when a~cut contains multiple edges of the minimum weight, all of them +are in the MST. It will however tell that if we pick one of these edges, an~arbitrary +MST can be modified to another MST that contains this edge. Therefore the Blue rule +will change to ``Pick a~cut~$C$ such that it does not contain any blue edge and color +one of its lightest edges blue.'' The Red lemma and the Red rule can be handled +in a~similar manner. The modified algorithm will be then guaranteed to find one of +the possible MST's. + +The Kruskal's and Jarn\'\i{}k's algorithms keep working. This is however not the case of the +Bor\o{u}vka's algorithm, whose proof of correctness in Lemma \ref{borcorr} explicitly referred to +distinct weights and indeed, if they are not distinct, the algorithm will occasionally produce +cycles. To avoid the cycles, the ties in edge weight comparisons have to be broken in a~systematic +way. The same applies to the contractive version of this algorithm. \endpart