]> mj.ucw.cz Git - saga.git/blob - mst.tex
Final typesetting: Chapters 1 and 2.
[saga.git] / mst.tex
1 \ifx\endpart\undefined
2 \input macros.tex
3 \fi
4
5 \chapter{Minimum Spanning Trees}
6
7 \section{The Problem}
8
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:
19
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:
22
23 \defn\id{mstdef}%
24 For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
25 \itemize\ibull
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 spanning subgraph of~$G$ 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
30   obvious sense.
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 among 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.
35 \endlist
36
37 Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
38 mostly geometric setting. He has discovered 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.
43
44 In the next 50 years, several significantly faster algorithms were discovered, ranging
45 from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
46 over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
47 and Pettie \cite{pettie:ackermann}, to an~algorithm by Pettie \cite{pettie:optimal}
48 whose time complexity is provably optimal.
49
50 In the upcoming chapters, we will explore this colorful universe of MST algorithms.
51 We will meet the canonical works of the classics, the clever ideas of their successors,
52 various approaches to the problem including randomization and solving of important
53 special cases. At several places, we will try to contribute our little stones to this
54 mosaic.
55
56 %--------------------------------------------------------------------------------
57
58 \section{Basic properties}\id{mstbasics}%
59
60 In this section, we will examine the basic properties of spanning trees and prove
61 several important theorems which will serve as a~foundation for our MST algorithms.
62 We will mostly follow the theory developed by Tarjan in~\cite{tarjan:dsna}.
63
64 For the whole section, we will fix a~connected graph~$G$ with edge weights~$w$ and all
65 other graphs will be spanning subgraphs of~$G$. We will use the same notation
66 for the subgraphs as for the corresponding sets of edges.
67
68 First of all, let us show that the weights on edges are not necessary for the
69 definition of the MST. We can formulate an equivalent characterization using
70 an~ordering of edges instead.
71
72 \defnn{Heavy and light edges}\id{heavy}%
73 Let~$T$ be a~spanning tree. Then:
74 \itemize\ibull
75 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ with~$y$.
76 \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
77   the edges of this path \df{edges covered by~$e$}.
78 \: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
79   is an~edge $f\in T[e]$ such that $w(f) > w(e)$.
80 \:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge.
81 \endlist
82
83 \rem
84 Edges of the tree~$T$ cover only themselves and thus they are neither heavy nor light.
85 The same can happen if an~edge outside~$T$ covers only edges of the same weight,
86 but this will be rare because all edge weights will be usually distinct.
87
88 \lemman{Light edges}\id{lightlemma}%
89 Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
90 is not minimum.
91
92 \proof
93 If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such
94 that $w(e')>w(e)$. Now $T-e'$ ($T$~with the edge~$e'$ removed) is a forest of two trees with endpoints of~$e$
95 located in different components, so adding $e$ to this forest must restore
96 connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T')
97 = w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum.
98 \qed
99
100 \figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\ref{lightlemma}}
101
102 The converse of this lemma is also true and to prove it, we will once again use
103 the technique of transforming trees by \df{exchanges of edges.} In the proof of the
104 lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
105 a~spanning tree for another edge~$f$ covered by~$e$, the result is again
106 a~spanning tree. In fact, it is possible to transform any spanning tree
107 to any other spanning tree by a sequence of exchanges.
108
109 \lemman{Exchange property for trees}\id{xchglemma}%
110 Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
111 a sequence of edge exchanges that transforms $T$ to~$T'$. More formally,
112 there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
113 $T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
114
115 \proof
116 By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$,
117 both trees are identical and no exchanges are needed. Otherwise, the trees are different,
118 but as they have the same number of edges, there must exist an edge $e'\in T'\setminus T$.
119 The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
120 exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
121 tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$. Now we can apply the induction
122 hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
123 \qed
124
125 \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\ref{xchglemma}}
126
127 \>In some cases, a~much stronger statement is true:
128
129 \lemman{Monotone exchanges}\id{monoxchg}%
130 Let $T$ be a spanning tree such that there are no $T$-light edges and $T'$
131 be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
132 transforming $T$ to~$T'$ such that the weight of the tree does not decrease in any step.
133
134 \proof
135 We improve the argument from the previous proof, refining the induction step.
136 When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
137 the weight never drops, since $e'$ is not a $T$-light edge and therefore
138 $w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\ge w(T)$.
139
140 To keep the induction going, we have to make sure that there are still no light
141 edges with respect to~$T^*$. In fact, it is enough to avoid such edges in
142 $T'\setminus T^*$, since these are the only edges considered by the induction
143 steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$
144 by picking the lightest such edge.
145
146 Let us consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not
147 $T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
148 either identical to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
149 where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter we have
150 $w(f)\ge w(e')$ due to the choice of~$e'$ and all other edges on~$C$ are lighter
151 than~$e'$ as $e'$ was not $T$-light.
152 \qed
153
154 This lemma immediately implies that Lemma \ref{lightlemma} works in both directions:
155
156 \thmn{Minimality of spanning trees}\id{mstthm}%
157 A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
158
159 \proof
160 If~$T$ is minimum, then by Lemma~\ref{lightlemma} there are no $T$-light
161 edges.
162 Conversely, when $T$ is a spanning tree without $T$-light edges
163 and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone
164 exchange lemma (\ref{monoxchg}) there exists a non-decreasing sequence
165 of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
166 and thus $T$~is also minimum.
167 \qed
168
169 In general, a single graph can have many minimum spanning trees (for example
170 a complete graph on~$n$ vertices with unit edge weights has $n^{n-2}$
171 minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
172 However, as the following theorem shows, this is possible only if the weight
173 function is not injective.
174
175 \thmn{Uniqueness of MST}%
176 If all edge weights are distinct, then the minimum spanning tree is unique.
177
178 \proof
179 Consider two minimum spanning trees $T_1$ and~$T_2$. According to the previous
180 theorem, there are no light edges with respect to neither of them, so by the
181 Monotone exchange lemma (\ref{monoxchg}) there exists a sequence of non-decreasing
182 edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
183 these edge exchanges must be in fact strictly increasing. On the other hand,
184 we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
185 $T_1$ and $T_2$ must be identical.
186 \looseness=1  %%HACK%%
187 \qed
188
189 \nota\id{mstnota}%
190 When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
191 its unique minimum spanning tree.
192
193 Also the following trivial lemma will be often invaluable:
194
195 \lemman{Edge removal}
196 Let~$G$ be a~graph with distinct edge weights and $e \in G\setminus\mst(G)$.
197 Then $\mst(G-e) = \mst(G)$.
198
199 \proof
200 The tree $T=\mst(G)$ is also a~MST of~$G-e$, because every $T$-light
201 edge in~$G-e$ is also $T$-light in~$G$. Then we apply the uniqueness of
202 the MST of~$G-e$.
203 \qed
204
205 \paran{Comparison oracles}\id{edgeoracle}%
206 To simplify the description of MST algorithms, we will assume that the weights
207 of all edges are distinct and that instead of numeric weights we are given a~comparison oracle.
208 The oracle is a~function that answers questions of type ``Is $w(e)<w(f)$?'' in
209 constant time. This will conveniently shield us from problems with representation
210 of real numbers in algorithms and in the few cases where we need a more concrete
211 input, we will explicitly state so.
212
213 In case the weights are not distinct, we can easily break ties by comparing some
214 unique identifiers of edges. According to our characterization of minimum spanning
215 trees, the unique MST of the new graph will still be a~MST of the original graph.
216 Sometimes, we could be interested in finding all solutions, but as this is an~uncommon
217 problem, we will postpone it until Section \ref{kbestsect}. For the time being,
218 we will always assume distinct weights.
219
220 \obs
221 If all edge weights are distinct and $T$~is an~arbitrary spanning tree, then every edge of~$G$
222 is either $T$-heavy, or $T$-light, or contained in~$T$.
223
224 \paran{Monotone isomorphism}%
225 Another useful consequence of the Minimality theorem is that whenever two graphs are isomorphic and the
226 isomorphism preserves the relative order of weights, the isomorphism applies to their MST's as well:
227
228 \defn
229 A~\df{monotone isomorphism} between two weighted graphs $G_1=(V_1,E_1,w_1)$ and
230 $G_2=(V_2,E_2,w_2)$ is a bijection $\pi: V_1\rightarrow V_2$ such that
231 for each $u,v\in V_1: uv\in E_1 \Leftrightarrow \pi(u)\pi(v)\in E_2$ and
232 for each $e,f\in E_1: w_1(e)<w_1(f) \Leftrightarrow w_2(\pi[e]) < w_2(\pi[f])$.
233
234 \lemman{MST of isomorphic graphs}\id{mstiso}%
235 Let~$G_1$ and $G_2$ be two weighted graphs with distinct edge weights and $\pi$
236 a~monotone isomorphism between them. Then $\mst(G_2) = \pi[\mst(G_1)]$.
237
238 \proof
239 The isomorphism~$\pi$ maps spanning trees to spanning trees bijectively and it preserves
240 the relation of covering. Since it is monotone, it preserves the property of
241 being a light edge (an~edge $e\in E(G_1)$ is $T$-light $\Leftrightarrow$
242 the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by the Minimality Theorem
243 (\ref{mstthm}), $T$ is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
244 \qed
245
246 %--------------------------------------------------------------------------------
247
248 \section{The Red-Blue meta-algorithm}
249
250 Most MST algorithms can be described as special cases of the following procedure
251 (again following Tarjan \cite{tarjan:dsna}):
252
253 \algn{Red-Blue Meta-Algorithm}\id{rbma}%
254 \algo
255 \algin A~graph $G$ with an edge comparison oracle (see \ref{edgeoracle})
256 \:At the beginning, all edges are colored black.
257 \:Apply rules as long as possible:
258 \::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
259 \::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}
260 \algout Minimum spanning tree of~$G$ consisting of edges colored blue.
261 \endalgo
262
263 \para
264 This procedure is not a proper algorithm, since it does not specify how to choose
265 the rule to apply. We will however prove that no matter how the rules are applied,
266 the procedure always stops and it gives the correct result. Also, it will turn out
267 that each of the classical MST algorithms can be described as a specific way
268 of choosing the rules in this procedure, which justifies the name meta-algorithm.
269
270 \nota
271 We will denote the unique minimum spanning tree of the input graph by~$T_{min}$.
272 We intend to prove that this is also the output of the procedure.
273
274 \paran{Correctness}%
275 Let us prove that the meta-algorithm is correct. First we show that the edges colored
276 blue in any step of the procedure always belong to~$T_{min}$ and that the edges colored
277 red are guaranteed to be outside~$T_{min}$. Then we demonstrate that the procedure
278 always stops. Some parts of the proof will turn out to be useful in the upcoming chapters,
279 so we will state them in a~slightly more general way.
280
281 \lemman{Blue lemma, also known as the Cut rule}\id{bluelemma}%
282 The lightest edge of every cut is contained in the MST.
283
284 \proof
285 By contradiction. Let $e$ be the lightest edge of a cut~$C$.
286 If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ that is
287 contained in~$C$ (take any pair of vertices separated by~$C$: the path
288 in~$T_{min}$ joining these vertices must cross~$C$ at least once). Exchanging
289 $e$ for $e'$ in $T_{min}$ yields an even lighter spanning tree since
290 $w(e)<w(e')$.
291 \qed
292
293 \lemman{Red lemma, also known as the Cycle rule}\id{redlemma}%
294 An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.
295
296 \proof
297 The implication from the left to the right follows directly from the Minimality
298 theorem: if~$e\not\in T_{min}$, then $e$~is $T_{min}$-heavy and so it is the heaviest
299 edge on the cycle $T_{min}[e]+e$.
300
301 We will prove the other implication again by contradiction. Suppose that $e$ is the heaviest edge of
302 a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split
303 to two components, let us call them $T_x$ and~$T_y$. Some vertices of~$C$ now lie in~$T_x$, the
304 others in~$T_y$, so there must exist in edge $e'\ne e$ such that its endpoints lie in different
305 components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields a~spanning tree lighter than
306 $T_{min}$.
307 \qed
308
309 \figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
310
311 \lemman{Black lemma}%
312 As long as there exists a black edge, at least one rule can be applied.
313
314 \proof
315 Assume that $e=xy$ is a black edge. Let us define~$M$ as the set of vertices
316 reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
317 with some blue path between $x$ and $y$ forms a cycle and $e$~must be the heaviest
318 edge on this cycle. This holds because all blue edges have been already proven
319 to be in $T_{min}$ and there can be no $T_{min}$-light edges.
320 In this case, we can apply the Red rule.
321
322 On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
323 and $V\setminus M$ contains no blue edges, therefore we can use the Blue rule.
324 \qed
325
326 \figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
327
328 \nota\id{deltanota}%
329 We will use $\delta(M)$ to denote the cut separating~$M$ from its complement.
330 That is, $\delta(M) = E \cap (M \times (V\setminus M))$. We will also abbreviate
331 $\delta(\{v\})$ as~$\delta(v)$.
332
333 \thmn{Red-Blue correctness}%
334 For any selection of rules, the Red-Blue procedure stops and the blue edges form
335 the minimum spanning tree of the input graph.
336
337 \proof
338 To prove that the procedure stops, let us notice that no edge is ever recolored,
339 so we must run out of black edges after at most~$m$ steps. Recoloring
340 to the same color is avoided by the conditions built in the rules, recoloring to
341 a different color would mean that the edge would be both inside and outside~$T_{min}$
342 due to our Red and Blue lemmata.
343
344 When no further rules can be applied, the Black lemma guarantees that all edges
345 are colored, so by the Blue lemma all blue edges are in~$T_{min}$ and by the Red
346 lemma all other (red) edges are outside~$T_{min}$. Thus the blue edges are exactly~$T_{min}$.
347 \qed
348
349 \rem
350 The MST problem is a~special case of the problem of finding the minimum basis
351 of a~weighted matroid. Surprisingly, when we modify the Red-Blue procedure to
352 use the standard definitions of cycles and cuts in matroids, it will always
353 find the minimum basis. Some of the other MST algorithms also easily generalize to
354 matroids and in some sense matroids are exactly the objects where ``the greedy approach works''. We
355 will however not pursue this direction in our work, referring the reader to the Oxley's monograph
356 \cite{oxley:matroids} instead.
357
358 %--------------------------------------------------------------------------------
359
360 \section{Classical algorithms}\id{classalg}%
361
362 The three classical MST algorithms (Bor\o{u}vka's, Jarn\'\i{}k's, and Kruskal's) can be easily
363 stated in terms of the Red-Blue meta-algorithm. For each of them, we first show the general version
364 of the algorithm, then we prove that it gives the correct result and finally we discuss the time
365 complexity of various implementations.
366
367 \paran{Bor\o{u}vka's algorithm}%
368 The oldest MST algorithm is based on a~simple idea: grow a~forest in a~sequence of
369 iterations until it becomes connected. We start with a~forest of isolated
370 vertices. In each iteration, we let each tree of the forest select the lightest
371 edge of those having exactly one endpoint in the tree (we will call such edges
372 the \df{neighboring edges} of the tree). We add all such edges to the forest and
373 proceed with the next iteration.
374
375 \algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst}, and others}
376 \algo
377 \algin A~graph~$G$ with an edge comparison oracle.
378 \:$T\=$ a forest consisting of vertices of~$G$ and no edges.
379 \:While $T$ is not connected:
380 \::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
381    separating $T_i$ from the rest of~$T$.
382 \::Add all $e_i$'s to~$T$.
383 \algout Minimum spanning tree~$T$.
384 \endalgo
385
386 \lemma\id{boruvkadrop}%
387 In each iteration of the algorithm, the number of trees in~$T$ decreases by at least
388 a~factor of two.
389
390 \proof
391 Each tree gets merged with at least one of its neighbors, so each of the new trees
392 contains two or more original trees.
393 \qed
394
395 \cor
396 The algorithm stops in $\O(\log n)$ iterations.
397
398 \lemma\id{borcorr}%
399 The Bor\o{u}vka's algorithm outputs the MST of the input graph.
400
401 \proof
402 In every iteration of the algorithm, $T$ is a blue subgraph,
403 because every addition of some edge~$e_i$ to~$T$ is a straightforward
404 application of the Blue rule. We stop when the blue subgraph is connected, so
405 we do not need the Red rule to explicitly exclude edges.
406
407 It remains to show that adding the edges simultaneously does not
408 produce a~cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
409 loss of generality we can assume that:
410 $$C=T_1[u_1,v_1]\,v_1u_2\,T_2[u_2,v_2]\,v_2u_3\,T_3[u_3,v_3]\, \ldots \,T_k[u_k,v_k]\,v_ku_1.$$
411 Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
412 or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation
413 of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and we can continue in the same way,
414 getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a~contradiction.
415 (Note that distinctness of edge weights was crucial here.)
416 \qed
417
418 \lemma\id{boruvkaiter}%
419 Each iteration can be carried out in time $\O(m)$.
420
421 \proof
422 We assign a label to each tree and we keep a mapping from vertices to the
423 labels of the trees they belong to. We scan all edges, map their endpoints
424 to the particular trees and for each tree we maintain the lightest incident edge
425 so far encountered. Instead of merging the trees one by one (which would be too
426 slow), we build an auxiliary graph whose vertices are the labels of the original
427 trees and edges correspond to the chosen lightest inter-tree edges. We find the connected
428 components of this graph, and these determine how are the original labels translated
429 to the new labels.
430 \qed
431
432 \thm
433 The Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
434
435 \proof
436 Follows from the previous lemmata.
437 \qed
438
439 \paran{Jarn\'\i{}k's algorithm}%
440 The next algorithm, discovered independently by Jarn\'\i{}k, Prim and Dijkstra, is similar
441 to the Bor\o{u}vka's algorithm, but instead of the whole forest it concentrates on
442 a~single tree. It starts with a~single vertex and it repeatedly extends the tree
443 by the lightest neighboring edge until the tree spans the whole graph.
444
445 \algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}%
446 \algo
447 \algin A~graph~$G$ with an edge comparison oracle.
448 \:$T\=$ a single-vertex tree containing an~arbitrary vertex of~$G$.
449 \:While there are vertices outside $T$:
450 \::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
451 \::$T\=T+uv$.
452 \algout Minimum spanning tree~$T$.
453 \endalgo
454
455 \lemma
456 The Jarn\'\i{}k's algorithm computes the MST of the input graph.
457
458 \proof
459 If~$G$ is connected, the algorithm always stops. In every step of
460 the algorithm, $T$ is always a blue tree. because Step~4 corresponds to applying
461 the Blue rule to the cut $\delta(T)$ separating~$T$ from the rest of the given graph. We need not care about
462 the remaining edges, since for a connected graph the algorithm always stops with the right
463 number of blue edges.
464 \qed
465
466 \impl\id{jarnimpl}%
467 The most important part of the algorithm is finding the \em{neighboring edges.}
468 In a~straightforward implementation, searching for the lightest neighboring
469 edge takes $\Theta(m)$ time, so the whole algorithm runs in time $\Theta(mn)$.
470
471 We can do much better by using a binary
472 heap to hold all neighboring edges. In each iteration, we find and delete the
473 minimum edge from the heap and once we expand the tree, we insert the newly discovered
474 neighboring edges to the heap and delete the neighboring edges that became
475 internal to the new tree. Since there are always at most~$m$ edges in the heap,
476 each heap operation takes $\O(\log m)=\O(\log n)$ time. For every edge, we perform
477 at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time in total.
478 From this, we can conclude:
479
480 \thm
481 The Jarn\'\i{}k's algorithm computes the MST of a~given graph in time $\O(m\log n)$.
482
483 \rem
484 We will show several faster implementations in section \ref{iteralg}.
485
486 \paran{Kruskal's algorithm}%
487 The last of the three classical algorithms processes the edges of the
488 graph~$G$ greedily. It starts with an~empty forest and it takes the edges of~$G$
489 in order of their increasing weights. For every edge, it checks whether its
490 addition to the forest produces a~cycle and if it does not, the edge is added.
491 Otherwise, the edge is dropped and not considered again.
492
493 \algn{Kruskal \cite{kruskal:mst}}
494 \algo
495 \algin A~graph~$G$ with an edge comparison oracle.
496 \:Sort edges of~$G$ by their increasing weights.
497 \:$T\=\hbox{an empty spanning subgraph}$.
498 \:For all edges $e$ in their sorted order:
499 \::If $T+e$ is acyclic, add~$e$ to~$T$.
500 \::Otherwise drop~$e$.
501 \algout Minimum spanning tree~$T$.
502 \endalgo
503
504 \lemma
505 The Kruskal's algorithm returns the MST of the input graph.
506
507 \proof
508 In every step, $T$ is a forest of blue trees. Adding~$e$ to~$T$
509 in step~4 applies the Blue rule on the cut separating some pair of components of~$T$ ($e$ is the lightest,
510 because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds
511 to the Red rule on the cycle found ($e$~must be the heaviest, since all other edges of the
512 cycle have been already processed). At the end of the algorithm, all edges are colored,
513 so~$T$ must be the~MST.
514 \qed
515
516 \impl
517 Except for the initial sorting, which in general requires $\Theta(m\log m)$ time, the only
518 other non-trivial operation is the detection of cycles. What we need is a~data structure
519 for maintaining connected components, which supports queries and edge insertion.
520 This is closely related to the well-known Disjoint Set Union problem:
521
522 \problemn{Disjoint Set Union, DSU}
523 Maintain an~equivalence relation on a~finite set under a~sequence of operations \<Union>
524 and \<Find>. The \<Find> operation tests whether two elements are equivalent and \<Union>
525 joins two different equivalence classes into one.
526
527 \para
528 We can maintain the connected components of our forest~$T$ as equivalence classes. When we want
529 to add an~edge~$uv$, we first call $\<Find>(u,v)$ to check if both endpoints of the edge lie in
530 the same component. If they do not, addition of this edge connects both components into one,
531 so we perform $\<Union>(u,v)$ to merge the equivalence classes.
532
533 Tarjan has shown that there is a~data structure for the DSU problem
534 of surprising efficiency:
535
536 \thmn{Disjoint Set Union, Tarjan \cite{tarjan:setunion}}\id{dfu}%
537 Starting with a~trivial equivalence with single-element classes, a~sequence of operations
538 comprising of $n$~\<Union>s intermixed with $m\ge n$~\<Find>s can be processed in time
539 $\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's function
540 (see Definition \ref{ackerinv}).
541
542 \proof
543 See \cite{tarjan:setunion}.
544 \qed
545
546 This completes the following theorem:
547
548 \thm\id{kruskal}%
549 The Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
550 If the edges are already sorted by their weights, the time drops to
551 $\O(m\timesalpha(m,n))$.
552
553 \proof
554 We spend $\O(m\log n)$ time on sorting, $\O(m\timesalpha(m,n))$ on processing the sequence
555 of \<Union>s and \<Find>s, and $\O(m)$ on all other work.
556 \qed
557
558 \rem
559 The cost of the \<Union> and \<Find> operations is of course dwarfed by the complexity
560 of sorting, so a much simpler (at least in terms of its analysis) data
561 structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
562 per operation. For example, we can label vertices with identifiers of the
563 corresponding components and always relabel the smaller of the two components.
564
565 We will study dynamic maintenance of connected components in more detail in Chapter~\ref{dynchap}.
566
567 %--------------------------------------------------------------------------------
568
569 \section{Contractive algorithms}\id{contalg}%
570
571 While the classical algorithms are based on growing suitable trees, they
572 can be also reformulated in terms of edge contraction. Instead of keeping
573 a~forest of trees, we can keep each tree contracted to a single vertex.
574 This replaces the relatively complex tree-edge incidencies by simple
575 vertex-edge incidencies, potentially speeding up the calculation at the
576 expense of having to perform the contractions.
577
578 We will show a contractive version of the Bor\o{u}vka's algorithm
579 in which these costs are carefully balanced, leading for example to
580 a linear-time algorithm for MST in planar graphs.
581
582 There are two definitions of edge contraction that differ when an edge of
583 a~triangle is contracted. Either we unify the other two edges to a single edge
584 or we keep them as two parallel edges, leaving us with a~multigraph. We will
585 use the multigraph version and we will show that we can easily reduce the multigraph
586 to a~simple graph later. (See \ref{contract} for the exact definitions.)
587
588 We only need to be able to map edges of the contracted graph to the original
589 edges, so we let each edge carry a unique label $\ell(e)$ that will be preserved by
590 contractions.
591
592 \lemman{Flattening a multigraph}\id{flattening}%
593 Let $G$ be a multigraph and $G'$ its subgraph obtaining by removing loops
594 and replacing each bundle of parallel edges by its lightest edge.
595 Then $G'$~has the same MST as~$G$.
596
597 \proof
598 Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction:
599 Loops can be never contained in a spanning tree. If there is a spanning tree~$T$
600 containing a~removed edge~$e$ parallel to an edge~$e'\in G'$, exchanging $e'$
601 for~$e$ makes~$T$ lighter. (This is indeed the multigraph version of the Red
602 lemma applied to a~two-edge cycle, as we will see in \ref{multimst}.)
603 \qed
604
605 \algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor}
606 \algo
607 \algin A~graph~$G$ with an edge comparison oracle.
608 \:$T\=\emptyset$.
609 \:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
610 \:While $n(G)>1$:
611 \::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$.
612 \::$T\=T\cup \{ \ell(e_1),\ldots,\ell(e_n) \}$.\hfil\break\cmt{Remember labels of all selected edges.}
613 \::Contract all edges $e_k$, inheriting labels and weights.\foot{In other words, we will ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
614 \::Flatten $G$ (remove parallel edges and loops).
615 \algout Minimum spanning tree~$T$.
616 \endalgo
617
618 \nota
619 For the analysis of the algorithm, we will denote the graph considered by the algorithm
620 at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and the number
621 of vertices and edges of this graph by $n_i$ and $m_i$ respectively. A~single iteration
622 of the algorithm will be called a~\df{Bor\o{u}vka step}.
623
624 \lemma\id{contiter}%
625 The $i$-th Bor\o{u}vka step can be carried out in time~$\O(m_i)$.
626
627 \proof
628 The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly
629 to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}):
630 We build an~auxiliary graph containing only the selected edges~$e_k$, find
631 connected components of this graph and renumber vertices in each component to
632 the identifier of the component. This takes $\O(m_i)$ time.
633
634 Flattening is performed by first removing the loops and then bucket-sorting the edges
635 (as ordered pairs of vertex identifiers) lexicographically, which brings parallel
636 edges together. The bucket sort uses two passes with $n_i$~buckets, so it takes
637 $\O(n_i+m_i)=\O(m_i)$.
638 \qed
639
640 \thm\id{contborthm}%
641 The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
642 time $\O(\min(n^2,m\log n))$.
643
644 \proof
645 As in the original Bor\o{u}vka's algorithm, the number of iterations is $\O(\log n)$.
646 When combined with the previous lemma, it gives an~$\O(m\log n)$ upper bound.
647
648 To get the $\O(n^2)$ bound, we observe that the number of trees in the non-contracting
649 version of the algorithm drops at least by a factor of two in each iteration (Lemma \ref{boruvkadrop})
650 and the same must hold for the number of vertices in the contracting version.
651 Therefore $n_i\le n/2^i$. While the number of edges need not decrease geometrically,
652 we still have $m_i\le n_i^2$ as the graphs~$G_i$ are simple (we explicitly removed multiple
653 edges and loops at the end of the previous iteration). Hence the total time spent
654 in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$.
655 \qed
656
657 On planar graphs, the algorithm runs much faster:
658
659 \thmn{Contractive Bor\o{u}vka on planar graphs}\id{planarbor}%
660 When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
661 time $\O(n)$.
662
663 \proof
664 Let us refine the previous proof. We already know that $n_i \le n/2^i$. We will
665 prove that when~$G$ is planar, the $m_i$'s are decreasing geometrically. We know that every
666 $G_i$ is planar, because the class of planar graphs is closed under edge deletion and
667 contraction. Moreover, $G_i$~is also simple, so we can use the standard bound on
668 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$.
669 The total time complexity of the algorithm is therefore $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$.
670 \qed
671
672 \rem
673 There are several other possibilities how to find the MST of a planar graph in linear time.
674 For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously
675 working on the graph and its topological dual. The advantage of our approach is that we do not need
676 to construct the planar embedding explicitly. We will show another simpler linear-time algorithm
677 in section~\ref{minorclosed}.
678
679 \rem
680 To achieve the linear time complexity, the algorithm needs a very careful implementation,
681 but we defer the technical details to section~\ref{bucketsort}.
682
683 \paran{General contractions}%
684 Graph contractions are indeed a~very powerful tool and they can be used in other MST
685 algorithms as well. The following lemma shows the gist:
686
687 \lemman{Contraction of MST edges}\id{contlemma}%
688 Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
689 produced by contracting~$e$ in~$G$, and $\pi$ the bijection between edges of~$G-e$ and
690 their counterparts in~$G/e$. Then $\mst(G) = \pi^{-1}[\mst(G/e)] + e.$
691
692 \proof
693 % We seem not to need this lemma for multigraphs...
694 %If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the
695 %Flattening lemma (\ref{flattening}), the MST stays the same and if we remove a parallel edge
696 %or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates
697 %in a MST.
698 The right-hand side of the equality is a spanning tree of~$G$. Let us denote it by~$T$ and
699 the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$
700 (by the Minimality Theorem, \ref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$,
701 then $\pi[T[f]]$ is a path covered by~$\pi(f)$ in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path.
702 In both cases, $f$ is $T'$-light, which contradicts the minimality of~$T'$. (We do not have
703 a~multigraph version of the theorem, but the direction we need is a~straightforward edge exchange,
704 which obviously works in multigraphs as well as in simple graphs.)
705 \qed
706
707 \rem
708 In the Contractive Bor\o{u}vka's algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$.
709
710 \paran{A~lower bound}%
711 Finally, we will show a family of graphs for which the $\O(m\log n)$ bound on time complexity
712 is tight. The graphs do not have unique weights, but they are constructed in a way that
713 the algorithm never compares two edges with the same weight. Therefore, when two such
714 graphs are monotonically isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way.
715
716 \defn
717 A~\df{distractor of order~$k$,} denoted by~$D_k$, is a path on $n=2^k$~vertices $v_1,\ldots,v_n$,
718 where each edge $v_iv_{i+1}$ has its weight equal to the number of trailing zeroes in the binary
719 representation of the number~$i$. The vertex $v_1$ is called a~\df{base} of the distractor.
720
721 \figure{distractor.eps}{\epsfxsize}{A~distractor $D_3$ and its evolution (bold edges are contracted)}
722
723 \rem
724 Alternatively, we can use a recursive definition: $D_0$ is a single vertex, $D_{k+1}$ consists
725 of two disjoint copies of~$D_k$ joined by an edge of weight~$k$.
726
727 \lemma
728 A~single iteration of the contractive algorithm reduces the distractor~$D_k$ to a~graph isomorphic with~$D_{k-1}$.
729
730 \proof
731 Each vertex~$v$ of~$D_k$ is incident with a single edge of weight~1. The algorithm therefore
732 selects all weight~1 edges and contracts them. This produces a~graph that is
733 equal to $D_{k-1}$ with all weights increased by~1, which does not change the relative order of edges.
734 \qed
735
736 \defn
737 A~\df{hedgehog}~$H_{a,k}$ is a graph consisting of $a$~distractors $D_k^1,\ldots,D_k^a$ of order~$k$
738 together with edges of a complete graph on the bases of these distractors. The additional edges
739 have arbitrary weights that are heavier than the edges of all the distractors.
740
741 \figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)}
742
743 \lemma
744 A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a~graph isomorphic with $H_{a,k-1}$.
745
746 \proof
747 Each vertex is incident with an edge of some distractor, so the algorithm does not select
748 any edge of the complete graph. Contraction therefore reduces each distractor to a smaller
749 distractor (modulo an additive factor in weight) and it leaves the complete graph intact.
750 The resulting graph is monotonely isomorphic to $H_{a,k-1}$.
751 \qed
752
753 When we set the parameters appropriately, we get the following lower bound:
754
755 \thmn{Lower bound for Contractive Bor\o{u}vka}%
756 For each $n$ there exists a graph on $\Theta(n)$ vertices and $\Theta(n)$ edges
757 such that the Contractive Bor\o{u}vka's algorithm spends time $\Omega(n\log n)$ on it.
758
759 \proof
760 Consider the hedgehog $H_{a,k}$ for $a=\lceil\sqrt n\rceil$ and $k=\lceil\log_2 a\rceil$.
761 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
762 as we wanted.
763
764 By the previous lemma, the algorithm proceeds through a sequence of hedgehogs $H_{a,k},
765 H_{a,k-1}, \ldots, H_{a,0}$ (up to monotone isomorphism), so it needs a logarithmic number of iterations plus some more
766 to finish on the remaining complete graph. Each iteration runs on a graph with $\Omega(n)$
767 edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
768 \qed
769
770 %--------------------------------------------------------------------------------
771
772 \section{Lifting restrictions}
773
774 In order to have a~simple and neat theory, we have introduced several restrictions
775 on the graphs in which we search for the MST. As in some rare cases we are going to
776 meet graphs that do not fit into this simplified world, let us quickly examine what
777 happens when the restrictions are lifted.
778
779 \paran{Disconnected graphs}\id{disconn}%
780 The basic properties of minimum spanning trees and the algorithms presented in
781 this chapter apply to minimum spanning forests of disconnected graphs, too.
782 The proofs of our theorems and the steps of our algorithms are based on adjacency
783 of vertices and existence of paths, so they are always local to a~single
784 connected component. The Bor\o{u}vka's and Kruskal's algorithm need no changes,
785 the Jarn\'\i{}k's algorithm has to be invoked separately for each component.
786
787 We can also extend the notion of light and heavy edges with respect
788 to a~tree to forests: When an~edge~$e$ connects two vertices lying in the same
789 tree~$T$ of a~forest~$F$, it is $F$-heavy iff it is $T$-heavy (similarly
790 for $F$-light). Edges connecting two different trees are always considered
791 $F$-light. Again, a~spanning forest~$F$ is minimum iff there are no $F$-light
792 edges.
793
794 \paran{Multigraphs}\id{multimst}%
795 All theorems and algorithms from this chapter work for multigraphs as well,
796 only the notation sometimes gets crabbed, which we preferred to avoid. The Minimality
797 theorem and the Blue rule stay unchanged. The Red rule is naturally extended to
798 self-loops (which are never in the MST) and two-edge cycles (where the heavier
799 edge can be dropped) as already suggested in the Flattening lemma (\ref{flattening}).
800
801 \paran{Multiple edges of the same weight}\id{multiweight}%
802 In case when the edge weights are not distinct, the characterization of minimum
803 spanning trees using light edges is still correct, but the MST is no longer unique
804 (as already mentioned, there can be as much as~$n^{n-2}$ MST's).
805
806 In the Red-Blue procedure, we have to avoid being too zealous. The Blue lemma cannot
807 guarantee that when a~cut contains multiple edges of the minimum weight, all of them
808 are in the MST. It will however tell that if we pick one of these edges, an~arbitrary
809 MST can be modified to another MST that contains this edge. Therefore the Blue rule
810 will change to ``Pick a~cut~$C$ such that it does not contain any blue edge and color
811 one of its lightest edges blue.'' The Red lemma and the Red rule can be handled
812 in a~similar manner. The modified algorithm will be then guaranteed to find one of
813 the possible MST's.
814
815 The Kruskal's and Jarn\'\i{}k's algorithms keep working. This is however not the case of the
816 Bor\o{u}vka's algorithm, whose proof of correctness in Lemma \ref{borcorr} explicitly referred to
817 distinct weights and indeed, if they are not distinct, the algorithm will occasionally produce
818 cycles. To avoid the cycles, the ties in edge weight comparisons have to be broken in a~systematic
819 way. The same applies to the contractive version of this algorithm.
820
821 \endpart