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 which 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\beta(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 survery the important algorithms for finding the MST and it
52 also presents several new ones.
54 \section{Basic Properties}
56 In this section, we will examine the basic properties of spanning trees and prove
57 several important theorems to base the algorithms upon. We will follow the theory
58 developed by Tarjan in~\cite{tarjan:dsna}.
60 For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all
61 other graphs will be spanning subgraphs of~$G$. We will use the same notation
62 for the subgraphs as for the corresponding sets of edges.
64 First of all, let us show that the weights on edges are not necessary for the
65 definition of the MST. We can formulate an equivalent characterization using
66 an ordering of edges instead.
68 \defnn{Heavy and light edges}\thmid{heavy}%
69 Let~$T$ be a~spanning tree. Then:
71 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
72 \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
73 the edges of this path \df{edges covered by~$e$}.
74 \: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
75 is an edge $f\in T[e]$ such that $w(f) > w(e)$.
76 \:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light.
80 Please note that the above properties also apply to tree edges
81 which by definition cover only themselves and therefore they are always heavy.
83 \lemman{Light edges}\thmid{lightlemma}%
84 Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
88 If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such
89 that $w(e')>w(e)$. Now $T-e'$ is a forest of two trees with endpoints of~$e$
90 located in different components, so adding $e$ to this forest must restore
91 connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T')
92 = w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum.
95 \figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}}
97 The converse of this lemma is also true and to prove it, we will once again use
98 technique of transforming trees by \df{exchanges} of edges. In the proof of the
99 lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
100 a spanning tree for another edge~$f$ covered by~$e$, the result is again
101 a spanning tree. In fact, it is possible to transform any spanning tree
102 to any other spanning tree by a sequence of exchanges.
104 \lemman{Exchange property for trees}\thmid{xchglemma}%
105 Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
106 a sequence of edge exchanges which transforms $T$ to~$T'$. More formally,
107 there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
108 $T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
111 By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$,
112 both trees are identical and no exchanges are needed. Otherwise, the trees are different,
113 but as they are of the same size, there must exist an edge $e'\in T'\setminus T$.
114 The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
115 exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
116 tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
117 hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
120 \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}}
122 \lemman{Monotone exchanges}\thmid{monoxchg}%
123 Let $T$ be a spanning tree such that there are no $T$-light edges and $T'$
124 be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
125 transforming $T$ to~$T'$ such that the weight does not increase in any step.
128 We improve the argument from the previous proof, refining the induction step.
129 When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
130 the weight never drops, since $e'$ is not a $T$-light edge and therefore
131 $w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\ge w(T)$.
133 To keep the induction going, we have to make sure that there are still no light
134 edges with respect to~$T^*$. In fact, it is enough to avoid such edges in
135 $T'\setminus T^*$, since these are the only edges considered by the induction
136 steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$
137 by picking the lightest such edge.
139 Now consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not
140 $T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
141 either equal to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
142 where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter one
143 $w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
144 than~$e'$ as $e'$ was not $T$-light.
148 A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
151 If~$T$ is minimum, then by Lemma~\thmref{lightlemma} there are no $T$-light
153 Conversely, when $T$ is a spanning tree without $T$-light edges
154 and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone
155 exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
156 of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
157 and thus $T$~is also minimum.
160 In general, a single graph can have many minimum spanning trees (for example
161 a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$
162 minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
163 However, as the following theorem shows, this is possible only if the weight
164 function is not injective.
166 \thmn{MST uniqueness}
167 If all edge weights are distinct, then the minimum spanning tree is unique.
170 Consider two minimum spanning trees $T_1$ and~$T_2$. According to the previous
171 theorem, there are no light edges with respect to neither of them, so by the
172 Monotone exchange lemma (\thmref{monoxchg}) there exists a sequence of non-decreasing
173 edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
174 these edge exchanges must be in fact strictly increasing. On the other hand,
175 we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
176 $T_1$ and $T_2$ must be identical.
179 \rem\thmid{edgeoracle}%
180 To simplify the description of MST algorithms, we will expect that the weights
181 of all edges are distinct and that instead of numeric weights (usually accompanied
182 by problems with representation of real numbers in algorithms) we will be given
183 a comparison oracle, that is a function which answers questions ``$w(e)<w(f)$?'' in
184 constant time. In case the weights are not distinct, we can easily break ties by
185 comparing some unique edge identifiers and according to our characterization of
186 minimum spanning trees, the unique MST of the new graph will still be a MST of the
187 original graph. In the few cases where we need a more concrete input, we will
190 \nota\thmid{mstnota}%
191 When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
192 its unique minimum spanning tree.
194 \section{The Red-Blue Meta-Algorithm}
196 Most MST algorithms can be described as special cases of the following procedure
197 (again following \cite{tarjan:dsna}):
199 \algn{Red-Blue Meta-Algorithm}
201 \algin A~graph $G$ with an edge comparison oracle (see \thmref{edgeoracle})
202 \:In the beginning, all edges are colored black.
203 \:Apply rules as long as possible:
204 \::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
205 \::Or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \hphantas{red.}{blue.} \cmt{Red rule}
206 \algout Minimum spanning tree of~$G$ consisting of edges colored blue.
210 This procedure is not a proper algorithm, since it does not specify how to choose
211 the rule to apply. We will however prove that no matter how the rules are applied,
212 the procedure always stops and gives the correct result. Also, it will turn out
213 that each of the classical MST algorithms can be described as a specific way
214 of choosing the rules in this procedure, which justifies the name meta-algorithm.
217 We will denote the unique minimum spanning tree of the input graph by~$T_{min}$.
218 We intend to prove that this is also the output of the procedure.
221 When an edge is colored blue in any step of the procedure, it is contained in the minimum spanning tree.
224 By contradiction. Let $e$ be an edge painted blue as the lightest edge of a cut~$C$.
225 If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ which is
226 contained in~$C$ (take any pair of vertices separated by~$C$, the path
227 in~$T_{min}$ joining these vertices must cross~$C$ at least once). Exchanging
228 $e$ for $e'$ in $T_{min}$ yields an even lighter spanning tree since
232 When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
235 Again by contradiction. Assume that $e$ is an edge painted red as the heaviest edge
236 of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
237 components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
238 the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
239 lie in different components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields
240 a lighter spanning tree than $T_{min}$.
243 \figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
246 As long as there exists a black edge, at least one rule can be applied.
249 Assume that $e=xy$ be a black edge. Let us denote $M$ the set of vertices
250 reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
251 with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest
252 edge on this cycle. This holds because all blue edges have been already proven
253 to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\thmref{mstthm}).
254 In this case we can apply the red rule.
256 On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
257 and $V(G)\setminus M$ contains no blue edges, therefore we can use the blue rule.
260 \figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
262 \thmn{Red-Blue correctness}
263 For any selection of rules, the Red-Blue procedure stops and the blue edges form
264 the minimum spanning tree of the input graph.
267 To prove that the procedure stops, let us notice that no edge is ever recolored,
268 so we must run out of black edges after at most~$m$ steps. Recoloring
269 to the same color is avoided by the conditions built in the rules, recoloring to
270 a different color would mean that the an edge would be both inside and outside~$T_{min}$
271 due to our Red and Blue lemmata.
273 When no further rules can be applied, the Black lemma guarantees that all edges
274 are colored, so by the Blue lemma all blue edges are in~$T_{min}$ and by the Red
275 lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
278 \section{Classical algorithms}
280 The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.
281 For each of them, we first state the general version of the algorithm, then we prove that
282 it gives the correct result and finally we discuss the time complexity of various
285 \algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
287 \algin A~graph~$G$ with an edge comparison oracle.
288 \:$T\=$ a forest consisting of vertices of~$G$ and no edges.
289 \:While $T$ is not connected:
290 \::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
291 separating $T_i$ from the rest of~$T$.
292 \::Add all $e_i$'s to~$T$.
293 \algout Minimum spanning tree~$T$.
297 Bor\o{u}vka's algorithm returns the MST of the input graph.
300 In every iteration of the algorithm, $T$ is a blue subgraph,
301 because every addition of some edge~$e_i$ to~$T$ is a straightforward
302 application of the Blue rule. We stop when the blue subgraph is connected, so
303 we do not need the Red rule to explicitly exclude edges.
305 It remains to show that adding the edges simultaneously does not
306 produce a cycle. Consider the first iteration of the algorithm where $T$ contains some cycle~$C$. Without
307 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$.
308 Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
309 or $v_{i-1}u_i$ (indexing cyclically). Assume that $e_1=v_1u_2$ (otherwise we reverse the orientation
310 of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and so on, giving $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$,
311 which is a contradiction. (Note that distinctness of edge weights was crucial here.)
314 \lemma\thmid{boruvkadrop}%
315 In each iteration of the algorithm, the number of trees in~$T$ drops at least twice.
318 Each tree gets merged with at least one neighboring trees, so each of the new trees
319 consists of at least two original trees.
323 The algorithm stops in $\O(\log n)$ iterations.
325 \lemma\thmid{boruvkaiter}%
326 Each iteration can be carried out in time $\O(m)$.
329 Following \cite{mm:mst},
330 we assign a label to each tree and we keep a mapping from vertices to the
331 labels of the trees they belong to. We scan all edges, map their endpoints
332 to the particular trees and for each tree we maintain the lightest incident edge
333 so far encountered. Instead of merging the trees one by one (which would be too
334 slow), we build an auxilliary graph whose vertices are labels of the original
335 trees and edges correspond to the chosen lightest inter-tree edges. We find connected
336 components of this graph, these determine how the original labels are translated
341 Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
344 Follows from the previous lemmata.
347 \algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}
349 \algin A~graph~$G$ with an edge comparison oracle.
350 \:$T\=$ a single-vertex tree containing any vertex of~$G$.
351 \:While there are vertices outside $T$:
352 \::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
354 \algout Minimum spanning tree~$T$.
358 Jarn\'\i{}k's algorithm returns the MST of the input graph.
361 During the course of the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying
362 the Blue rule to a cut between~$T$ and the rest of the given graph. We need not care about
363 the remaining edges, since for a connected graph the algorithm always stops with the right
364 number of blue edges.
368 The most important part of the algorithm is finding \em{neighboring edges,} i.e., edges
369 going between $T$ and $V(G)\setminus T$. In the straightforward implementation,
370 searching for the lightest neighboring edge takes $\Theta(m)$ time, so the whole
371 algorithm runs in time $\Theta(mn)$.
373 We can do much better by using a binary
374 heap to hold all neighboring edges. In each iteration, we find and delete the
375 minimum edge from the heap and once we expand the tree, we insert the newly discovered
376 neighboring edges to the heap while deleting the neighboring edges which become
377 internal to the new tree. Since there are always at most~$m$ edges in the heap,
378 each heap operation takes $\O(\log m)=\O(\log n)$ time. For every edge, we perform
379 at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time in total.
380 From this, we can conclude:
383 Jarn\'\i{}k's algorithm finds the MST of the graph in time $\O(m\log n)$.
386 We will show several faster implementations in section \secref{fibonacci}.
388 \algn{Kruskal \cite{kruskal:mst}, the Greedy algorithm}
390 \algin A~graph~$G$ with an edge comparison oracle.
391 \:Sort edges of~$G$ by their increasing weight.
392 \:$T\=\emptyset$. \cmt{an empty spanning subgraph}
393 \:For all edges $e$ in their sorted order:
394 \::If $T+e$ is acyclic, add~$e$ to~$T$.
395 \::Otherwise drop~$e$.
396 \algout Minimum spanning tree~$T$.
400 Kruskal's algorithm returns the MST of the input graph.
403 In every step, $T$ is a forest of blue trees. Adding~$e$ to~$T$
404 in step~4 applies the Blue rule on the cut separating two components of~$T$ ($e$ is the lightest,
405 because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds
406 to the red rule on the cycle found ($e$~must be the heaviest, since all other edges of the
407 cycle have been already processed). At the end of the algorithm, all edges have been colored,
408 so~$T$ must be the~MST.
412 Except for the initial sorting, which in general takes $\Theta(m\log n)$ time, the only
413 other non-trivial operation is detection of cycles. What we need is a data structure
414 for maintaining connected components, which supports queries and edge insertion.
415 The following theorem shows that it can be done with a surprising efficiency.
417 \thmn{Incremental connectivity}
418 When only edge insertions and queries are allowed, connected components
419 can be maintained in $\O(\alpha(n))$ time amortized per operation.
422 Proven by Tarjan and van Leeuwen in \cite{tarjan:setunion}.
425 \FIXME{Define Ackermann's function. Use $\alpha(m,n)$?}
428 The cost of the operations on components is of course dwarfed by the complexity
429 of sorting, so a much simpler (at least in terms of its analysis) data
430 structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
431 per operation. For example, we can label vertices with identifiers of the
432 corresponding components and always recolor the smaller of the two components.
435 Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$
436 or $\O(m\alpha(n))$ if the edges are already sorted by their weights.
439 Follows from the above analysis.
442 \section{Contractive algorithms}
444 While the classical algorithms are based on growing suitable trees, they
445 can be also reformulated in terms of edge contraction. Instead of keeping
446 a forest of trees, we can keep each tree contracted to a single vertex.
447 This replaces the relatively complex tree-edge incidencies by simple
448 vertex-edge incidencies, potentially speeding up the calculation at the
449 expense of having to perform the contractions.
451 We will show a contractive version of the Bor\o{u}vka's algorithm
452 in which these costs are carefully balanced, leading for example to
453 a linear-time algorithm for MST in planar graphs.
455 There are two definitions of edge contraction which differ when an edge of a
456 triangle is contracted. Either we unify the other two edges to a single edge
457 or we keep them as two parallel edges, leaving us with a multigraph. We will
458 use the multigraph version and show that we can easily reduce the multigraph
459 to a simple graph later. (See \thmref{contract} for the exact definitions.)
461 We only need to be able to map edges of the contracted graph to the original
462 edges, so each edge will carry a unique label $\ell(e)$ which will be preserved by
465 \lemman{Flattening a multigraph}\thmid{flattening}%
466 Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been
467 removed and each bundle of parallel edges replaced by its lightest edge.
468 Then $G'$~has the same MST as~$G$.
471 Loops can be never used in a spanning tree. If there is a spanning tree~$T$
472 containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
473 for~$e$ in~$T$ makes it lighter. \qed
475 \rem Removal of the heavier of a pair of parallel edges can be also viewed
476 as an application of the Red rule on a two-edge cycle. And indeed it is, the
477 Red-Blue procedure works on multigraphs as well as on simple graphs and all the
478 classical algorithms also do. We only would have to be more careful in the
479 formulations and proofs, which we preferred to avoid. We also note that most of
480 the algorithms can be run on disconnected multigraphs with little or no
483 \algn{Contracting version of Bor\o{u}vka's algorithm}
485 \algin A~graph~$G$ with an edge comparison oracle.
487 \:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
489 \::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$.
490 \::$T\=T\cup \{ \ell(e_i) \}$. \cmt{Remember labels of all selected edges.}
491 \::Contract $G$ along all edges $e_i$, inheriting labels and weights.
492 \::Flatten $G$, removing parallel edges and loops.
493 \algout Minimum spanning tree~$T$.
497 Each iteration of the algorithm can be carried out in time~$\O(m)$.
500 The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly
501 to the unions in the original Bor\o{u}vka's algorithm (see \thmref{boruvkaiter}).
502 We build an auxillary graph containing only the selected edges~$e_i$, find
503 connected components of this graph and renumber vertices in each component to
504 the identifier of the component. This takes $\O(m)$ time.
506 Flattening is performed by first removing the loops and then bucket-sorting the edges
507 (as ordered pairs of vertex identifiers) lexicographically, which brings parallel
508 edges together. The bucket sort uses two passes with $n$~buckets, so it takes
513 The Contracting Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
516 As in the original Bor\o{u}vka's algorithm, the number of phases is $\O(\log n)$.
517 Then apply the previous lemma.
521 When the input graph is planar, the Contracting Bor\o{u}vka's algorithm runs in
525 Let us denote the graph considered by the algorithm at the beginning of the $i$-th
526 iteration by $G_i$ (starting with $G_0=G$) and its number of vertices and edges
527 by $n_i$ and $m_i$ respectively. As we already know from the previous lemma,
528 the $i$-th iteration takes $\O(m_i)$ time. We are going to prove that the
529 $m_i$'s are decreasing exponentially.
531 The number of trees in the non-contracting version of the algorithm decreases
532 at least twice in each iteration (Lemma \thmref{boruvkadrop}) and therefore the
533 same must hold for the number of vertices in the contracting version. So $n_i\le n/2^i$.
535 However, every $G_i$ is planar, because the class of planar graphs is closed
536 under edge deletion and contraction. The~$G_i$ is also simple as we explicitly removed multiple edges and
537 loops at the end of the previous iteration. So we can use the standard theorem on
538 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$.
539 From this we get that the total time complexity is $\O(\sum_i m_i)=\O(m)$.
543 There are other possibilities how to find the MST of a planar graph in linear time.
544 Matsui \cite{matsui:planar} has described an algorithm based on simultaneously
545 processing the graph and its dual. The advantage of our approach is that we do not
546 need to construct the planar embedding first.
549 To achieve the linear time complexity, the algorithm needs a very careful implementation.
550 Specifically, when we represent the graph using adjacency lists, whose heads are stored
551 in an array indexed by vertex identifiers, we must renumber the vertices in each iteration.
552 Otherwise, unused identifiers could end up taking most of space in the arrays and scans of these
553 arrays would have super-linear cost with respect to the size of the current graph~$G_i$.
556 The algorithm can be also implemented on the pointer machine. Representation of graphs
557 by pointer structures easily avoids the aforementioned problems with sparse arrays,
558 but we need to handle the bucket sorting somehow. We can create a small data structure
559 for every vertex and use a pointer to this structure as a unique identifier of the vertex.
560 We will also keep a list of all vertex structures. During the bucket sort, each vertex
561 structure will contain a pointer to the corresponding bucket and the vertex list will
562 define the order of vertices (which can be arbitrary, but has to be fixed).
564 Graph contractions are a very powerful tool and they can be used in other MST
565 algorithms as well. The following lemma shows the gist:
567 \lemman{Contraction of MST edges}
568 Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
569 produced by contracting $G$ along~$e$, and $\pi$ the bijection between edges of~$G-e$ and
570 their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$
573 % We seem not to need this lemma for multigraphs...
574 %If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the
575 %Flattening lemma (\thmref{flattening}), the MST stays the same and if we remove a parallel edge
576 %or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates
578 The right-hand side of the equality is a spanning tree of~$G$, let us denote it by~$T$ and
579 the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$.
580 If the path $T[f]$ covered by~$f$ does not contain~$e$, then $\pi[T[f]]$ is a path covered by~$\pi(f)$
581 in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path. In both cases, $f$ is $T'$-light, which should
582 contradict the minimality of~$T'$, but we need a multigraph version of Theorem \thmref{mstthm}
583 which we did not prove.
585 To avoid it, we consider the flattening~$F$ of~$G/e$ and apply the theorem to it.
586 According to the Flattening lemma (\thmref{flattening}), $F$~has the same MST as~$G/e$
587 and therefore it contains all edges of~$T'$. If $\pi(f)\not\in E(F)$, it
588 has been removed in favor of some lighter edge~$f'$ and if $\pi(f)$ was
589 $T$-light, then $f'$ is even so.
593 In the previous algorithm, the role of the mapping~$\pi^{-1}$ is played by the edge labels~$\ell$.
595 \section{Minor-closed graph classes}
597 \section{Using Fibonacci heaps}
600 % G has to be connected, so m=O(n)
601 % mention Steiner trees