X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=mst.tex;h=efc4d63238fe433e81007b922e78d9487b477198;hb=3ce379fec86d6348c80aa1d8c77fb64a0dbada13;hp=7014cfa3328e427ae32cbd721779f370de43a562;hpb=9d944002861dfbc3e35320ea196f611a1e030282;p=saga.git diff --git a/mst.tex b/mst.tex index 7014cfa..efc4d63 100644 --- a/mst.tex +++ b/mst.tex @@ -24,7 +24,7 @@ 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. @@ -41,25 +41,27 @@ 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\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 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. %-------------------------------------------------------------------------------- -\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. @@ -75,12 +77,13 @@ Let~$T$ be a~spanning tree. Then: 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$ 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$ @@ -105,7 +108,7 @@ 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'$. @@ -124,7 +127,7 @@ hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence. \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 does not decrease in any step. \proof We improve the argument from the previous proof, refining the induction step. @@ -146,7 +149,7 @@ $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}% +\thmn{Minimality of spanning trees}\id{mstthm}% A~spanning tree~$T$ is minimum iff there is no $T$-light edge. \proof @@ -165,7 +168,7 @@ 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 @@ -178,49 +181,66 @@ 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\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) +and \. The \ operation tests whether two elements are equivalent and \ +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 $\(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 $\(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$~\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}% +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 \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\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 -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. @@ -486,8 +565,8 @@ 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 we will show that we can easily reduce the multigraph to a simple graph later. (See \ref{contract} for the exact definitions.) @@ -504,14 +583,10 @@ 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. +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 @@ -519,89 +594,83 @@ formulations and proofs, which we preferred to avoid. \:$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 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 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 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. +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. -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$. +To achieve the linear time complexity, the algorithm needs a very careful implementation, +but we defer the technical details to section~\ref{bucketsort}. -\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). - -\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: \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 +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 @@ -622,10 +691,11 @@ which obviously works in multigraphs as well.) \rem In the previous 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$ @@ -681,446 +751,53 @@ edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices. %-------------------------------------------------------------------------------- -\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. -\:\ all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly. -\:While $H$ is not empty: -\::$(u,v)\=\(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)$, \ $A(w)$ to~$(v,w)$ in~$H$. -\:::If there is no such edge, then \ $(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 -\:\ (insertion of a~new element) in $\O(1)$, -\:\ (decreasing value of an~existing element) in $\O(1)$, -\:\ (merging of two heaps into one) in $\O(1)$, -\:\ (deletion of the minimal element) in $\O(\log n)$, -\:\ (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 \ or \ per edge and exactly one \ -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. - -\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. \, \ 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. \ and \ 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$ \'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 +\section{Lifting restrictions} + +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. + +\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. + +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. -% 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 +\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