5 \chapter{Minimum Spanning Trees}
9 The problem of finding a minimum spanning tree of a weighted graph is one of the
10 best studied problems in the area of combinatorial optimization since its birth.
11 Its colorful history (see \cite{graham:msthistory} and \cite{nesetril:history} for the full account)
12 begins in~1926 with the pioneering work of Bor\o{u}vka
13 \cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
14 who studied primarily an Euclidean version of the problem related to planning
15 of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
16 algorithm for the general version of the problem. As it was well before the dawn of graph
17 theory, the language of his paper was complicated, so we will better state the problem
18 in contemporary terminology:
20 \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
21 find its minimum spanning tree, defined as follows:
24 For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
26 \:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
27 \:A~\df{spanning tree} of $G$ is any its spanning subgraph that is a tree.
28 \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
29 When comparing two weights, we will use the terms \df{lighter} and \df{heavier} in the
31 \:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$
32 is the smallest possible of all the spanning trees of~$G$.
33 \:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as
34 a union of (minimum) spanning trees of its connected components.
37 Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
38 mostly geometric setting, giving another efficient algorithm. However, when
39 computer science and graph theory started forming in the 1950's and the
40 spanning tree problem was one of the central topics of the flourishing new
41 disciplines, the previous work was not well known and the algorithms had to be
42 rediscovered several times.
44 Recently, several significantly faster algorithms were discovered, most notably the
45 $\O(m\timesbeta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
46 algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
47 and Pettie \cite{pettie:ackermann}.
49 \FIXME{Write the rest of the history.}
51 This chapter attempts to survey the important algorithms for finding the MST and it
52 also presents several new ones.
54 %--------------------------------------------------------------------------------
56 \section{Basic properties}
58 In this section, we will examine the basic properties of spanning trees and prove
59 several important theorems to base the algorithms upon. We will follow the theory
60 developed by Tarjan in~\cite{tarjan:dsna}.
62 For the whole section, we will fix a~connected graph~$G$ with edge weights~$w$ and all
63 other graphs will be spanning subgraphs of~$G$. We will use the same notation
64 for the subgraphs as for the corresponding sets of edges.
66 First of all, let us show that the weights on edges are not necessary for the
67 definition of the MST. We can formulate an equivalent characterization using
68 an ordering of edges instead.
70 \defnn{Heavy and light edges}\id{heavy}%
71 Let~$T$ be a~spanning tree. Then:
73 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
74 \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
75 the edges of this path \df{edges covered by~$e$}.
76 \: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
77 is an edge $f\in T[e]$ such that $w(f) > w(e)$.
78 \:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge.
82 Edges of the tree~$T$ itself are neither heavy nor light. We will sometimes
83 use the name \df{non-heavy} for edges which are either light or contained
86 \lemman{Light edges}\id{lightlemma}%
87 Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
91 If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such
92 that $w(e')>w(e)$. Now $T-e'$ is a forest of two trees with endpoints of~$e$
93 located in different components, so adding $e$ to this forest must restore
94 connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T')
95 = w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum.
98 \figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\ref{lightlemma}}
100 The converse of this lemma is also true and to prove it, we will once again use
101 technique of transforming trees by \df{exchanges} of edges. In the proof of the
102 lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
103 a spanning tree for another edge~$f$ covered by~$e$, the result is again
104 a spanning tree. In fact, it is possible to transform any spanning tree
105 to any other spanning tree by a sequence of exchanges.
107 \lemman{Exchange property for trees}\id{xchglemma}%
108 Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
109 a sequence of edge exchanges that transforms $T$ to~$T'$. More formally,
110 there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
111 $T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
114 By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$,
115 both trees are identical and no exchanges are needed. Otherwise, the trees are different,
116 but as they are of the same size, there must exist an edge $e'\in T'\setminus T$.
117 The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
118 exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
119 tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
120 hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
123 \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\ref{xchglemma}}
125 \lemman{Monotone exchanges}\id{monoxchg}%
126 Let $T$ be a spanning tree such that there are no $T$-light edges and $T'$
127 be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
128 transforming $T$ to~$T'$ such that the weight does not increase in any step.
131 We improve the argument from the previous proof, refining the induction step.
132 When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
133 the weight never drops, since $e'$ is not a $T$-light edge and therefore
134 $w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\ge w(T)$.
136 To keep the induction going, we have to make sure that there are still no light
137 edges with respect to~$T^*$. In fact, it is enough to avoid such edges in
138 $T'\setminus T^*$, since these are the only edges considered by the induction
139 steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$
140 by picking the lightest such edge.
142 Now consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not
143 $T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
144 either equal to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
145 where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter one
146 $w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
147 than~$e'$ as $e'$ was not $T$-light.
150 \thmn{Minimality by order}\id{mstthm}%
151 A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
154 If~$T$ is minimum, then by Lemma~\ref{lightlemma} there are no $T$-light
156 Conversely, when $T$ is a spanning tree without $T$-light edges
157 and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone
158 exchange lemma (\ref{monoxchg}) there exists a non-decreasing sequence
159 of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
160 and thus $T$~is also minimum.
163 In general, a single graph can have many minimum spanning trees (for example
164 a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$
165 minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
166 However, as the following theorem shows, this is possible only if the weight
167 function is not injective.
169 \thmn{MST uniqueness}%
170 If all edge weights are distinct, then the minimum spanning tree is unique.
173 Consider two minimum spanning trees $T_1$ and~$T_2$. According to the previous
174 theorem, there are no light edges with respect to neither of them, so by the
175 Monotone exchange lemma (\ref{monoxchg}) there exists a sequence of non-decreasing
176 edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
177 these edge exchanges must be in fact strictly increasing. On the other hand,
178 we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
179 $T_1$ and $T_2$ must be identical.
183 To simplify the description of MST algorithms, we will expect that the weights
184 of all edges are distinct and that instead of numeric weights (usually accompanied
185 by problems with representation of real numbers in algorithms) we will be given
186 a comparison oracle, that is a function which answers questions ``$w(e)<w(f)$?'' in
187 constant time. In case the weights are not distinct, we can easily break ties by
188 comparing some unique edge identifiers and according to our characterization of
189 minimum spanning trees, the unique MST of the new graph will still be a MST of the
190 original graph. In the few cases where we need a more concrete input, we will
194 When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
195 its unique minimum spanning tree.
197 Another useful consequence is that whenever two graphs are isomorphic and the
198 isomorphism preserves weight order, the isomorphism applies to their MST's
202 A~\df{monotone isomorphism} of two weighted graphs $G_1=(V_1,E_1,w_1)$ and
203 $G_2=(V_2,E_2,w_2)$ is a bijection $\pi: V_1\rightarrow V_2$ such that
204 for each $u,v\in V_1: uv\in E_1 \Leftrightarrow \pi(u)\pi(v)\in E_2$ and
205 for each $e,f\in E_1: w_1(e)<w_1(f) \Leftrightarrow w_2(\pi[e]) < w_2(\pi[f])$.
207 \lemman{MST of isomorphic graphs}\id{mstiso}%
208 Let~$G_1$ and $G_2$ be two weighted graphs with unique edge weights and $\pi$
209 their monotone isomorphism. Then $\mst(G_2) = \pi[\mst(G_1)]$.
212 The isomorphism~$\pi$ maps spanning trees onto spanning trees and it preserves
213 the relation of covering. Since it is monotone, it preserves the property of
214 being a light edge (an~edge $e\in E(G_1)$ is $T$-light $\Leftrightarrow$
215 the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by Theorem~\ref{mstthm}, $T$
216 is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
219 %--------------------------------------------------------------------------------
221 \section{The Red-Blue meta-algorithm}
223 Most MST algorithms can be described as special cases of the following procedure
224 (again following \cite{tarjan:dsna}):
226 \algn{Red-Blue Meta-Algorithm}\id{rbma}%
228 \algin A~graph $G$ with an edge comparison oracle (see \ref{edgeoracle})
229 \:In the beginning, all edges are colored black.
230 \:Apply rules as long as possible:
231 \::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
232 \::or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \rack{blue.}{red.\hfil} \cmt{Red rule}
233 \algout Minimum spanning tree of~$G$ consisting of edges colored blue.
237 This procedure is not a proper algorithm, since it does not specify how to choose
238 the rule to apply. We will however prove that no matter how the rules are applied,
239 the procedure always stops and gives the correct result. Also, it will turn out
240 that each of the classical MST algorithms can be described as a specific way
241 of choosing the rules in this procedure, which justifies the name meta-algorithm.
244 We will denote the unique minimum spanning tree of the input graph by~$T_{min}$.
245 We intend to prove that this is also the output of the procedure.
247 \lemman{Blue lemma}\id{bluelemma}%
248 When an edge is colored blue in any step of the procedure, it is contained in the minimum spanning tree.
251 By contradiction. Let $e$ be an edge painted blue as the lightest edge of a cut~$C$.
252 If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ that is
253 contained in~$C$ (take any pair of vertices separated by~$C$, the path
254 in~$T_{min}$ joining these vertices must cross~$C$ at least once). Exchanging
255 $e$ for $e'$ in $T_{min}$ yields an even lighter spanning tree since
258 \lemman{Red lemma}\id{redlemma}%
259 When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
262 Again by contradiction. Suppose that $e$ is an edge painted red as the heaviest edge
263 of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
264 components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
265 the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
266 lie in different components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields
267 a lighter spanning tree than $T_{min}$.
270 \figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
272 \lemman{Black lemma}%
273 As long as there exists a black edge, at least one rule can be applied.
276 Assume that $e=xy$ be a black edge. Let us denote $M$ the set of vertices
277 reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
278 with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest
279 edge on this cycle. This holds because all blue edges have been already proven
280 to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\ref{mstthm}).
281 In this case we can apply the red rule.
283 On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
284 and $V(G)\setminus M$ contains no blue edges, therefore we can use the blue rule.
287 \figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
289 \thmn{Red-Blue correctness}%
290 For any selection of rules, the Red-Blue procedure stops and the blue edges form
291 the minimum spanning tree of the input graph.
294 To prove that the procedure stops, let us notice that no edge is ever recolored,
295 so we must run out of black edges after at most~$m$ steps. Recoloring
296 to the same color is avoided by the conditions built in the rules, recoloring to
297 a different color would mean that the an edge would be both inside and outside~$T_{min}$
298 due to our Red and Blue lemmata.
300 When no further rules can be applied, the Black lemma guarantees that all edges
301 are colored, so by the Blue lemma all blue edges are in~$T_{min}$ and by the Red
302 lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
306 The Red lemma actually works in both directions and it can be used to characterize
307 all non-MST edges, which will turn out to be useful in the latter chapters.
309 \corn{Cycle rule}\id{cyclerule}%
310 An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.
313 The implication from the right to the left is the Red lemma. In the other
314 direction, when~$e$ is not contained in~$T_{min}$, it is $T_{min}$-heavy (by
315 Theorem \ref{mstthm}), so it is the heaviest edge on the cycle $T_{min}[e]+e$.
318 %--------------------------------------------------------------------------------
320 \section{Classical algorithms}\id{classalg}%
322 The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.
323 For each of them, we first show the general version of the algorithm, then we prove that
324 it gives the correct result and finally we discuss the time complexity of various
327 \paran{Bor\o{u}vka's algorithm}%
328 The oldest MST algorithm is based on a~simple idea: grow a~forest in a~sequence of
329 iterations until it becomes connected. We start with a~forest of isolated
330 vertices. In each iteration, we let each tree of the forest select the lightest
331 edge of those having exactly one endpoint in the tree (we will call such edges
332 the \df{neighboring edges} of the tree). We add all such edges to the forest and
333 pAroceed with the next iteration.
335 \algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
337 \algin A~graph~$G$ with an edge comparison oracle.
338 \:$T\=$ a forest consisting of vertices of~$G$ and no edges.
339 \:While $T$ is not connected:
340 \::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
341 separating $T_i$ from the rest of~$T$.
342 \::Add all $e_i$'s to~$T$.
343 \algout Minimum spanning tree~$T$.
346 \lemma\id{boruvkadrop}%
347 In each iteration of the algorithm, the number of trees in~$T$ drops at least twice.
350 Each tree gets merged with at least one of its neighbors, so each of the new trees
351 contains two or more original trees.
355 The algorithm stops in $\O(\log n)$ iterations.
358 Bor\o{u}vka's algorithm outputs the MST of the input graph.
361 In every iteration of the algorithm, $T$ is a blue subgraph,
362 because every addition of some edge~$e_i$ to~$T$ is a straightforward
363 application of the Blue rule. We stop when the blue subgraph is connected, so
364 we do not need the Red rule to explicitly exclude edges.
366 It remains to show that adding the edges simultaneously does not
367 produce a cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
368 loss of generality we can assume that $C=T_1[u_1v_1]\,v_1u_2\,T_2[u_2v_2]\,v_2u_3\,T_3[u_3v_3]\, \ldots \,T_k[u_kv_k]\,v_ku_1$.
369 Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
370 or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation
371 of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and we can continue in the same way,
372 getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction.
373 (Note that distinctness of edge weights was crucial here.)
376 \lemma\id{boruvkaiter}%
377 Each iteration can be carried out in time $\O(m)$.
380 We assign a label to each tree and we keep a mapping from vertices to the
381 labels of the trees they belong to. We scan all edges, map their endpoints
382 to the particular trees and for each tree we maintain the lightest incident edge
383 so far encountered. Instead of merging the trees one by one (which would be too
384 slow), we build an auxilliary graph whose vertices are the labels of the original
385 trees and edges correspond to the chosen lightest inter-tree edges. We find connected
386 components of this graph, these determine how are the original labels translated
391 Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
394 Follows from the previous lemmata.
397 \paran{Jarn\'\i{}k's algorithm}%
398 The next algorithm, discovered independently by Jarn\'\i{}k, Prim and Dijkstra, is similar
399 to Bor\o{u}vka's algorithm, but instead of the whole forest it concentrates on
400 a~single tree. It starts with a~single vertex and it repeatedly extends the tree
401 by the lightest neighboring edge until it spans the whole graph.
403 \algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}%
405 \algin A~graph~$G$ with an edge comparison oracle.
406 \:$T\=$ a single-vertex tree containing an~arbitrary vertex of~$G$.
407 \:While there are vertices outside $T$:
408 \::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
410 \algout Minimum spanning tree~$T$.
414 Jarn\'\i{}k's algorithm computers the MST of the input graph.
417 If~$G$ is connected, the algorithm always stops. Let us prove that in every step of
418 the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying
419 the Blue rule to the cut $\delta(T)$ separating~$T$ from the rest of the given graph. We need not care about
420 the remaining edges, since for a connected graph the algorithm always stops with the right
421 number of blue edges.
425 The most important part of the algorithm is finding \em{neighboring edges.}
426 In a~straightforward implementation, searching for the lightest neighboring
427 edge takes $\Theta(m)$ time, so the whole algorithm runs in time $\Theta(mn)$.
429 We can do much better by using a binary
430 heap to hold all neighboring edges. In each iteration, we find and delete the
431 minimum edge from the heap and once we expand the tree, we insert the newly discovered
432 neighboring edges to the heap while deleting the neighboring edges that become
433 internal to the new tree. Since there are always at most~$m$ edges in the heap,
434 each heap operation takes $\O(\log m)=\O(\log n)$ time. For every edge, we perform
435 at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time in total.
436 From this, we can conclude:
439 Jarn\'\i{}k's algorithm finds the MST of a~given graph in time $\O(m\log n)$.
442 We will show several faster implementations in section \ref{fibonacci}.
444 \paran{Kruskal's algorithm}%
445 The last of the three classical algorithms processes the edges of the
446 graph~$G$ greedily. It starts with an~empty forest and it takes the edges of~$G$
447 in order of their increasing weights. For every edge, it checks whether its
448 addition to the forest produces a~cycle and if it does not, the edge is added.
449 Otherwise, the edge is dropped and not considered again.
451 \algn{Kruskal \cite{kruskal:mst}}
453 \algin A~graph~$G$ with an edge comparison oracle.
454 \:Sort edges of~$G$ by their increasing weights.
455 \:$T\=\emptyset$. \cmt{an empty spanning subgraph}
456 \:For all edges $e$ in their sorted order:
457 \::If $T+e$ is acyclic, add~$e$ to~$T$.
458 \::Otherwise drop~$e$.
459 \algout Minimum spanning tree~$T$.
463 Kruskal's algorithm returns the MST of the input graph.
466 In every step, $T$ is a forest of blue trees. Adding~$e$ to~$T$
467 in step~4 applies the Blue rule on the cut separating some pair of components of~$T$ ($e$ is the lightest,
468 because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds
469 to the Red rule on the cycle found ($e$~must be the heaviest, since all other edges of the
470 cycle have been already processed). At the end of the algorithm, all edges are colored,
471 so~$T$ must be the~MST.
475 Except for the initial sorting, which in general takes $\Theta(m\log m)$ time, the only
476 other non-trivial operation is the detection of cycles. What we need is a~data structure
477 for maintaining connected components, which supports queries and edge insertion.
478 This is closely related to the well-known Disjoint Set Union problem:
480 \problemn{Disjoint Set Union (DSU)}
481 Maintain an~equivalence relation on a~finite set under a~sequence of operations \<Union>
482 and \<Find>. The \<Find> operation tests whether two elements are equivalent and \<Union>
483 joins two different equivalence classes into one.
486 We can maintain the connected components of our forest~$T$ as equivalence classes. When we want
487 to add an~edge~$uv$, we first call $\<Find>(u,v)$ to check if both endpoints of the edge lie in
488 the same components. If they do not, addition of this edge connects both components into one,
489 so we perform $\<Union>(u,v)$ to merge the equivalence classes.
491 Tarjan and van Leeuwen have shown that there is a~data structure for the DSU problem
492 with surprising efficiency:
494 \thmn{Disjoint Set Union, Tarjan and van Leeuwen \cite{tarjan:setunion}}\id{dfu}%
495 Starting with a~trivial equivalence with single-element classes, a~sequence of operations
496 comprising of $n$~\<Union>s intermixed with $m\ge n$~\<Find>s can be processed in time
497 $\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's function
498 (see Definition \ref{ackerinv}).
501 See \cite{tarjan:setunion}.
504 This completes the following theorem:
507 Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
508 If the edges are already sorted by their weights, the time drops to
509 $\O(m\timesalpha(m,n))$.
512 We spend $\O(m\log n)$ on sorting, $\O(m\timesalpha(m,n))$ on processing the sequence
513 of \<Union>s and \<Find>s, and $\O(m)$ on all other work.
517 The cost of the \<Union> and \<Find> operations is of course dwarfed by the complexity
518 of sorting, so a much simpler (at least in terms of its analysis) data
519 structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
520 per operation. For example, we can label vertices with identifiers of the
521 corresponding components and always relabel the smaller of the two components.
523 We will study dynamic maintenance of connected components in more detail in Chapter~\ref{dynchap}.
525 %--------------------------------------------------------------------------------
527 \section{Contractive algorithms}\id{contalg}%
529 While the classical algorithms are based on growing suitable trees, they
530 can be also reformulated in terms of edge contraction. Instead of keeping
531 a forest of trees, we can keep each tree contracted to a single vertex.
532 This replaces the relatively complex tree-edge incidencies by simple
533 vertex-edge incidencies, potentially speeding up the calculation at the
534 expense of having to perform the contractions.
536 We will show a contractive version of the Bor\o{u}vka's algorithm
537 in which these costs are carefully balanced, leading for example to
538 a linear-time algorithm for MST in planar graphs.
540 There are two definitions of edge contraction that differ when an edge of
541 a~triangle is contracted. Either we unify the other two edges to a single edge
542 or we keep them as two parallel edges, leaving us with a~multigraph. We will
543 use the multigraph version and we will show that we can easily reduce the multigraph
544 to a simple graph later. (See \ref{contract} for the exact definitions.)
546 We only need to be able to map edges of the contracted graph to the original
547 edges, so each edge will carry a unique label $\ell(e)$ that will be preserved by
550 \lemman{Flattening a multigraph}\id{flattening}%
551 Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been
552 removed and each bundle of parallel edges replaced by its lightest edge.
553 Then $G'$~has the same MST as~$G$.
556 Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction:
557 Loops can be never contained in a spanning tree. If there is a spanning tree~$T$
558 containing a~removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
559 for~$e$ makes~$T$ lighter. \qed
561 \rem Removal of the heavier of a pair of parallel edges can be also viewed
562 as an application of the Red rule on a two-edge cycle. And indeed it is, the
563 Red-Blue procedure works on multigraphs as well as on simple graphs and all the
564 classical algorithms also do. We would only have to be more careful in the
565 formulations and proofs, which we preferred to avoid.
567 \algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor}
569 \algin A~graph~$G$ with an edge comparison oracle.
571 \:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
573 \::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$.
574 \::$T\=T\cup \{ \ell(e_k) \}$. \cmt{Remember labels of all selected edges.}
575 \::Contract $G$ along all edges $e_k$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
576 \::Flatten $G$, removing parallel edges and loops.
577 \algout Minimum spanning tree~$T$.
581 For the analysis of the algorithm, we will denote the graph considered by the algorithm
582 at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and the number
583 of vertices and edges of this graph by $n_i$ and $m_i$ respectively.
586 The $i$-th iteration of the algorithm (also called the Bor\o{u}vka step) can be carried
587 out in time~$\O(m_i)$.
590 The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly
591 to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}):
592 We build an auxillary graph containing only the selected edges~$e_k$, find
593 connected components of this graph and renumber vertices in each component to
594 the identifier of the component. This takes $\O(m_i)$ time.
596 Flattening is performed by first removing the loops and then bucket-sorting the edges
597 (as ordered pairs of vertex identifiers) lexicographically, which brings parallel
598 edges together. The bucket sort uses two passes with $n_i$~buckets, so it takes
599 $\O(n_i+m_i)=\O(m_i)$.
603 The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
604 time $\O(\min(n^2,m\log n))$.
607 As in the original Bor\o{u}vka's algorithm, the number of iterations is $\O(\log n)$.
608 When combined with the previous lemma, it gives an~$\O(m\log n)$ upper bound.
610 To get the $\O(n^2)$ bound, we observe that the number of trees in the non-contracting
611 version of the algorithm drops at least by a factor of two in each iteration (Lemma \ref{boruvkadrop})
612 and the same must hold for the number of vertices in the contracting version.
613 Therefore $n_i\le n/2^i$. While the number of edges need not decrease geometrically,
614 we still have $m_i\le n_i^2$ as the graphs~$G_i$ are simple (we explicitly removed multiple
615 edges and loops at the end of the previous iteration). Hence the total time spent
616 in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$.
619 \thmn{Contractive Bor\o{u}vka on planar graphs, \cite{mm:mst}}\id{planarbor}%
620 When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
624 Let us refine the previous proof. We already know that $n_i \le n/2^i$. We will
625 prove that when~$G$ is planar, the $m_i$'s are decreasing geometrically. We know that every
626 $G_i$ is planar, because the class of planar graphs is closed under edge deletion and
627 contraction. Moreover, $G_i$~is also simple, so we can use the standard theorem on
628 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$.
629 The total time complexity of the algorithm is therefore $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$.
633 There are several other possibilities how to find the MST of a planar graph in linear time.
634 For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously
635 working on the graph and its topological dual. The advantage of our approach is that we do not need
636 to construct the planar embedding explicitly. We will show one more linear algorithm
637 in section~\ref{minorclosed}.
640 To achieve the linear time complexity, the algorithm needs a very careful implementation,
641 but we defer the technical details to section~\ref{bucketsort}.
644 Graph contractions are indeed a~very powerful tool and they can be used in other MST
645 algorithms as well. The following lemma shows the gist:
647 \lemman{Contraction of MST edges}\id{contlemma}%
648 Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
649 produced by contracting $G$ along~$e$, and $\pi$ the bijection between edges of~$G-e$ and
650 their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$
653 % We seem not to need this lemma for multigraphs...
654 %If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the
655 %Flattening lemma (\ref{flattening}), the MST stays the same and if we remove a parallel edge
656 %or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates
658 The right-hand side of the equality is a spanning tree of~$G$, let us denote it by~$T$ and
659 the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$
660 (by Theorem \ref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$,
661 then $\pi[T[f]]$ is a path covered by~$\pi(f)$ in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path.
662 In both cases, $f$ is $T'$-light, which contradicts the minimality of~$T'$. (We do not have
663 a~multigraph version of the theorem, but the side we need is a~straightforward edge exchange,
664 which obviously works in multigraphs as well.)
668 In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$.
671 Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity
672 is tight. The graphs do not have unique weights, but they are constructed in a way that
673 the algorithm never compares two edges with the same weight. Therefore, when two such
674 graphs are monotonely isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way.
677 A~\df{distractor of order~$k$,} denoted by~$D_k$, is a path on $n=2^k$~vertices $v_1,\ldots,v_n$
678 where each edge $v_iv_{i+1}$ has its weight equal to the number of trailing zeroes in the binary
679 representation of the number~$i$. The vertex $v_1$ is called a~\df{base} of the distractor.
682 Alternatively, we can use a recursive definition: $D_0$ is a single vertex, $D_{k+1}$ consists
683 of two disjoint copies of~$D_k$ joined by an edge of weight~$k$.
685 \figure{distractor.eps}{\epsfxsize}{A~distractor $D_3$ and its evolution (bold edges are contracted)}
688 A~single iteration of the contractive algorithm reduces~$D_k$ to a graph isomorphic with~$D_{k-1}$.
691 Each vertex~$v$ of~$D_k$ is incident with a single edge of weight~1. The algorithm therefore
692 selects all weight~1 edges and contracts them. This produces a graph which is
693 exactly $D_{k-1}$ with all weights increased by~1, which does not change the relative order of edges.
697 A~\df{hedgehog}~$H_{a,k}$ is a graph consisting of $a$~distractors $D_k^1,\ldots,D_k^a$ of order~$k$
698 together with edges of a complete graph on the bases of the distractors. These additional edges
699 have arbitrary weights, but heavier than the edges of all distractors.
701 \figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)}
704 A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a graph isomorphic with $H_{a,k-1}$.
707 Each vertex is incident with an edge of some distractor, so the algorithm does not select
708 any edge of the complete graph. Contraction therefore reduces each distractor to a smaller
709 distractor (modulo an additive factor in weight) and leaves the complete graph intact.
710 This is monotonely isomorphic to $H_{a,k-1}$.
713 \thmn{Lower bound for Contractive Bor\o{u}vka}%
714 For each $n$ there exists a graph on $\Theta(n)$ vertices and $\Theta(n)$ edges
715 such that the Contractive Bor\o{u}vka's algorithm spends time $\Omega(n\log n)$ on it.
718 Consider the hedgehog $H_{a,k}$ for $a=\lceil\sqrt n\rceil$ and $k=\lceil\log_2 a\rceil$.
719 It has $a\cdot 2^k = \Theta(n)$ vertices and ${a \choose 2} + a\cdot 2^k = \Theta(a^2) + \Theta(a^2) = \Theta(n)$ edges
722 By the previous lemma, the algorithm proceeds through a sequence of hedgehogs $H_{a,k},
723 H_{a,k-1}, \ldots, H_{a,0}$ (up to monotone isomorphism), so it needs a logarithmic number of iterations plus some more
724 to finish on the remaining complete graph. Each iteration runs on a graph with $\Omega(n)$
725 edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
728 \remn{Disconnected graphs}\id{disconn}%
729 The basic properties of minimum spanning trees and the algorithms presented in
730 this chapter apply to minimum spanning forests of disconnected graphs, too.
731 The proofs of our theorems and the steps of our algorithms are based on adjacency
732 of vertices and existence of paths, so they are always local to a~single
733 connected component. The Bor\o{u}vka's and Kruskal's algorithm need no changes,
734 the Jarn\'\i{}k's algorithm has to be invoked separately for each component.
736 We can also extend the notion of light and heavy edges with respect
737 to a~tree to forests: When an~edge~$e$ connects two vertices lying in the same
738 tree~$T$ of a~forest~$F$, it is $F$-heavy iff it is $T$-heavy (similarly
739 for $F$-light). Edges connecting two different trees are always considered
740 $F$-light. Again, a~spanning forest~$F$ is minimum iff there are no $F$-light