]> mj.ucw.cz Git - saga.git/blob - adv.tex
Special cases.
[saga.git] / adv.tex
1 \ifx\endpart\undefined
2 \input macros.tex
3 \fi
4
5 \chapter{Advanced MST Algorithms}
6
7 \section{Minor-closed graph classes}\id{minorclosed}%
8
9 The contractive algorithm given in section~\ref{contalg} has been found to perform
10 well on planar graphs, but in the general case its time complexity was not linear.
11 Can we find any broader class of graphs where the algorithm is still efficient?
12 The right context turns out to be the minor-closed graph classes, which are
13 closed under contractions and have bounded density.
14
15 \defn\id{minordef}%
16 A~graph~$H$ is a \df{minor} of a~graph~$G$ (written as $H\minorof G$) iff it can be obtained
17 from a~subgraph of~$G$ by a sequence of simple graph contractions (see \ref{simpcont}).
18
19 \defn
20 A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and
21 its every minor~$H$, the graph~$H$ lies in~$\cal C$ as well. A~class~$\cal C$ is called
22 \df{non-trivial} if at least one graph lies in~$\cal C$ and at least one lies outside~$\cal C$.
23
24 \example
25 Non-trivial minor-closed classes include:
26 \itemize\ibull
27 \:planar graphs,
28 \:graphs embeddable in any fixed surface (i.e., graphs of bounded genus),
29 \:graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles,
30 \:graphs of bounded tree-width or path-width.
31 \endlist
32
33 \para
34 Many of the nice structural properties of planar graphs extend to
35 minor-closed classes, too (see \cite{lovasz:minors} for a~nice survey
36 of this theory and \cite{diestel:gt} for some of the deeper results).
37 The most important property is probably the characterization
38 of such classes in terms of their forbidden minors.
39
40 \defn
41 For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class
42 of graphs which do not contain any of the graphs in~$\cal H$ as a~minor.
43 We will call $\cal H$ the set of \df{forbidden (or excluded) minors} for this class.
44 We will often abbreviate $\Forb(\{M_1,\ldots,M_n\})$ to $\Forb(M_1,\ldots,M_n)$.
45
46 \obs
47 For every~${\cal H}\ne\emptyset$, the class $\Forb({\cal H})$ is non-trivial
48 and closed on minors. This works in the opposite direction as well: for every
49 minor-closed class~$\cal C$ there is a~class $\cal H$ such that ${\cal C}=\Forb({\cal H})$.
50 One such~$\cal H$ is the complement of~$\cal C$, but smaller ones can be found, too.
51 For example, the planar graphs can be equivalently described as the class $\Forb(K_5, K_{3,3})$
52 --- this follows from the Kuratowski's theorem (the theorem speaks of forbidden
53 subdivisions, but while in general this is not the same as forbidden minors, it
54 is for $K_5$ and $K_{3,3}$). The celebrated theorem by Robertson and Seymour
55 guarantees that we can always find a~finite set of forbidden minors.
56
57 \thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
58 For every non-trivial minor-closed graph class~$\cal C$ there exists
59 a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$.
60
61 \proof
62 This theorem has been proven in a~long series of papers on graph minors
63 culminating with~\cite{rs:wagner}. See this paper and follow the references
64 to the previous articles in the series.
65 \qed
66
67 \para
68 For analysis of the contractive algorithm,
69 we will make use of another important property --- the bounded density of
70 minor-closed classes. The connection between minors and density dates back to
71 Mader in the 1960's and it can be proven without use of the Robertson-Seymour
72 theorem.
73
74 \defn\id{density}%
75 Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$
76 to be the infimum of all~$\varrho$'s such that $m(G) \le \varrho\cdot n(G)$
77 holds for every $G\in\cal C$.
78
79 \thmn{Mader \cite{mader:dens}}
80 For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
81 of average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph.
82
83 \proofsketch
84 (See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.)
85
86 Let us fix~$k$ and prove by induction on~$m$ that every graph of average
87 degree at least~$2^m$ contains a~subdivision of some graph with $k$~vertices
88 and ${k\choose 2}\ge m\ge k$~edges. For $m={k\choose 2}$ the theorem follows
89 as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$.
90
91 The base case $m=k$: Let us observe that when the average degree
92 is~$a$, removing any vertex of degree less than~$a/2$ does not decrease the
93 average degree. A~graph with $a\ge 2^k$ therefore has a~subgraph
94 with minimum degree $\delta\ge a/2=2^{k-1}$. Such subgraph contains
95 a~cycle on more than~$\delta$ vertices, in other words a~subdivision of
96 the cycle~$C_k$.
97
98 Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and
99 assume that the theorem already holds for $m-1$. Without loss of generality,
100 $G$~is connected. Consider a~maximal set $U\subseteq V$ such that the subgraph $G[U]$
101 induced by~$U$ is connected and the graph $G.U$ ($G$~with $U$~contracted to
102 a~single vertex) has average degree at least~$2^m$ (such~$U$ exists, because
103 $G=G.U$ whenever $\vert U\vert=1$). Now consider the subgraph~$H$ induced
104 in~$G$ by the neighbors of~$U$. Every $v\in V(H)$ must have $\deg_H(v) \ge 2^{m-1}$,
105 as otherwise we can add this vertex to~$U$, contradicting its
106 maximality. By the induction hypothesis, $H$ contains a~subdivision of some
107 graph~$R$ with $r$~vertices and $m-1$ edges. Any two non-adjacent vertices
108 of~$R$ can be connected in the subdivision by a~path lying entirely in~$G[U]$,
109 which reveals a~subdivision of a~graph with $m$~edges. \qed
110
111 \thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
112 Every non-trivial minor-closed class of graphs has finite edge density.
113
114 \proof
115 Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$.
116 As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(K_x)$, so
117 $\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the
118 theorem for classes excluding a~single complete graph~$K_x$.
119
120 We will show that $\varrho({\cal C})\le 2h(x)$, where $h$~is the function
121 from the previous theorem. If any $G\in{\cal C}$ had more than $2h(x)\cdot n(G)$
122 edges, its average degree would be at least~$h(x)$, so by the previous theorem
123 $G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor.
124 \qed
125
126 \rem
127 Minor-closed classes share many other interesting properties, as shown for
128 example by Theorem 6.1 of \cite{nesetril:minors}.
129
130 \thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}%
131 For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
132 algorithm (\ref{contbor}) finds the MST of any graph of this class in time
133 $\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
134
135 \proof
136 Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered
137 by the algorithm at the beginning of the $i$-th iteration by~$G_i$ and its number of vertices
138 and edges by $n_i$ and $m_i$ respectively. Again the $i$-th phase runs in time $\O(m_i)$
139 and $n_i \le n/2^i$, so it remains to show a linear bound for the $m_i$'s.
140
141 Since each $G_i$ is produced from~$G_{i-1}$ by a sequence of edge contractions,
142 all $G_i$'s are minors of~$G$.\foot{Technically, these are multigraph contractions,
143 but followed by flattening, so they are equivalent to contractions on simple graphs.}
144 So they also belong to~$\cal C$ and by the previous theorem $m_i\le \varrho({\cal C})\cdot n_i$.
145 \qed
146
147 \rem\id{nobatch}%
148 The contractive algorithm uses ``batch processing'' to perform many contractions
149 in a single step. It is also possible to perform contractions one edge at a~time,
150 batching only the flattenings. A~contraction of an edge~$uv$ can be done
151 in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back
152 with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small
153 degrees. The following lemma shows that this is always the case in minor-closed
154 classes.
155
156 \lemman{Low-degree vertices}\id{lowdeg}%
157 Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph
158 with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$.
159
160 \proof
161 Assume the contrary: Let there be at least $n/2$ vertices with degree
162 greater than~$4\varrho$.  Then $\sum_v \deg(v) > n/2
163 \cdot 4\varrho = 2\varrho n$, which is in contradiction with the number
164 of edges being at most $\varrho n$.
165 \qed
166
167 \rem
168 The proof can be also viewed
169 probabilistically: let $X$ be the degree of a vertex of~$G$ chosen uniformly at
170 random. Then ${\bb E}X \le 2\varrho$, hence by the Markov's inequality
171 ${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have
172 $\deg(v)\le 4\varrho$.
173
174 \algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}%
175 \algo
176 \algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
177 \:$T\=\emptyset$.
178 \:$\ell(e)\=e$ for all edges~$e$.
179 \:While $n(G)>1$:
180 \::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
181 \:::Select the lightest edge~$e$ incident with~$v$.
182 \:::Contract~$G$ along~$e$.
183 \:::$T\=T + \ell(e)$.
184 \::Flatten $G$, removing parallel edges and loops.
185 \algout Minimum spanning tree~$T$.
186 \endalgo
187
188 \thm
189 When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the
190 Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$ 
191 finds the MST of any graph from this class in time $\O(n)$. (The constant
192 in the~$\O$ depends on~the class.)
193
194 \proof
195 Let us denote by $G_i$, $n_i$ and $m_i$ the graph considered by the
196 algorithm at the beginning of the $i$-th iteration of the outer loop,
197 and the number of its vertices and edges respectively. As in the proof
198 of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s
199 are minors of the graph~$G$ given as the input.
200
201 For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
202 guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
203 have degree at most~$t$. Each selected edge removes one such vertex and
204 possibly increases the degree of another, so at least $n_i/4$ edges get selected.
205 Hence $n_i\le 3/4\cdot n_{i-1}$ and therefore $n_i\le n\cdot (3/4)^i$ and the
206 algorithm terminates after $\O(\log n)$ iterations.
207
208 Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
209 the trivial cut $\delta(v)$ (see the Blue Rule in \ref{rbma}).
210 The steps 6 and~7 therefore correspond to the operation
211 described by the Lemma on contraction of MST edges (\ref{contlemma}) and when
212 the algorithm stops, $T$~is indeed the minimum spanning tree.
213
214 It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have
215 $m_i\le \varrho n_i \le \varrho n/2^i$.
216 We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
217 Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
218 over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$.
219 Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting
220 Bor\o{u}vka's Algorithm (see \ref{contiter}).
221
222 The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
223 \qed
224
225 \rem
226 For planar graphs, we can get a sharper version of the low-degree lemma,
227 showing that the algorithm works with $t=8$ as well (we had $t=12$ as
228 $\varrho=3$). While this does not change the asymptotic time complexity
229 of the algorithm, the constant-factor speedup can still delight the hearts of
230 its practical users.
231
232 \lemman{Low-degree vertices in planar graphs}%
233 Let $G$ be a planar graph with $n$~vertices. Then at least $n/2$ vertices of~$v$
234 have degree at most~8.
235
236 \proof
237 It suffices to show that the lemma holds for triangulations (if there
238 are any edges missing, the situation can only get better) with at
239 least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$.
240 The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
241 so by the same argument as in the proof of the general lemma, for at least $n/2$
242 vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$.
243 \qed
244
245 \rem\id{hexa}%
246 The constant~8 in the previous lemma is the best we can have.
247 Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them
248 lie on the outer face and have degrees at most~6, the remaining $n-\O(k)$ interior
249 vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$,
250 ignoring terms of order $\O(k)$. All interior triangles can be properly colored with
251 two colors, black and white. Now add a~new vertex inside each white face and connect
252 it to all three vertices on the boundary of that face. This adds $f/2 \approx n$
253 vertices of degree~3 and it increases the degrees of the original $\approx n$ interior
254 vertices to~9, therefore about a half of the vertices of the new planar graph
255 has degree~9.
256
257 \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
258
259 \rem
260 The observation in~Theorem~\ref{mstmcc} was also made by Gustedt in~\cite{gustedt:parallel},
261 who studied a~parallel version of the contractive Bor\o{u}vka's algorithm applied
262 to minor-closed classes.
263
264 %--------------------------------------------------------------------------------
265
266 \section{Using Fibonacci heaps}
267 \id{fibonacci}
268
269 We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
270 Fredman and Tarjan have shown a~faster implementation in~\cite{ft:fibonacci}
271 using their Fibonacci heaps. In this section, we convey their results and we
272 show several interesting consequences.
273
274 The previous implementation of the algorithm used a binary heap to store all edges
275 separating the current tree~$T$ from the rest of the graph, i.e., edges of the cut~$\delta(T)$.
276 Instead of that, we will remember the vertices adjacent to~$T$ and for each such vertex~$v$ we
277 will maintain the lightest edge~$uv$ such that $u$~lies in~$T$. We will call these edges \df{active edges}
278 and keep them in a~Fibonacci heap, ordered by weight.
279
280 When we want to extend~$T$ by the lightest edge of~$\delta(T)$, it is sufficient to
281 find the lightest active edge~$uv$ and add this edge to~$T$ together with the new vertex~$v$.
282 Then we have to update the active edges as follows. The edge~$uv$ has just ceased to
283 be active. We scan all neighbors~$w$ of the vertex~$v$. When $w$~is in~$T$, no action
284 is needed. If $w$~is outside~$T$ and it was not adjacent to~$T$ (there is no active edge
285 remembered for it so far), we set the edge~$vw$ as active. Otherwise we check the existing
286 active edge for~$w$ and replace it by~$vw$ if the new edge is lighter.
287
288 The following algorithm shows how these operations translate to insertions, decreases
289 and deletions on the heap.
290
291 \algn{Active Edge Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}%
292 \algo
293 \algin A~graph~$G$ with an edge comparison oracle.
294 \:$v_0\=$ an~arbitrary vertex of~$G$.
295 \:$T\=$ a tree containing just the vertex~$v_0$.
296 \:$H\=$ a~Fibonacci heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(uv)$, initially empty.
297 \:$A\=$ a~mapping of vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
298 \:\<Insert> all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly.
299 \:While $H$ is not empty:
300 \::$(u,v)\=\<DeleteMin>(H)$.
301 \::$T\=T+uv$.
302 \::For all edges $vw$ such that $w\not\in T$:
303 \:::If there exists an~active edge~$A(w)$:
304 \::::If $vw$ is lighter than~$A(w)$, \<Decrease> $A(w)$ to~$(v,w)$ in~$H$.
305 \:::If there is no such edge, then \<Insert> $(v,w)$ to~$H$ and set~$A(w)$.
306 \algout Minimum spanning tree~$T$.
307 \endalgo
308
309 \para
310 To analyze the time complexity of this algorithm, we will use the standard
311 theorem on~complexity of the Fibonacci heap:
312
313 \thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations
314 with the indicated amortized time complexities:
315 \itemize\ibull
316 \:\<Insert> (insertion of a~new element) in $\O(1)$,
317 \:\<Decrease> (decreasing value of an~existing element) in $\O(1)$,
318 \:\<Merge> (merging of two heaps into one) in $\O(1)$,
319 \:\<DeleteMin> (deletion of the minimal element) in $\O(\log n)$,
320 \:\<Delete> (deletion of an~arbitrary element) in $\O(\log n)$,
321 \endlist
322 \>where $n$ is the number of elements present in the heap at the time of
323 the operation.
324
325 \proof
326 See Fredman and Tarjan \cite{ft:fibonacci} for both the description of the Fibonacci
327 heap and the proof of this theorem.
328 \qed
329
330 \thm
331 Algorithm~\ref{jarniktwo} with the Fibonacci heap finds the MST of the input graph in time~$\O(m+n\log n)$.
332
333 \proof
334 The algorithm always stops, because every edge enters the heap~$H$ at most once.
335 As it selects exactly the same edges as the original Jarn\'\i{}k's algorithm,
336 it gives the correct answer.
337
338 The time complexity is $\O(m)$ plus the cost of the heap operations. The algorithm
339 performs at most one \<Insert> or \<Decrease> per edge and exactly one \<DeleteMin>
340 per vertex. There are at most $n$ elements in the heap at any given time,
341 thus by the previous theorem the operations take $\O(m+n\log n)$ time in total.
342 \qed
343
344 \cor
345 For graphs with edge density at least $\log n$, this algorithm runs in linear time.
346
347 \rem
348 We can consider using other kinds of heaps which have the property that inserts
349 and decreases are faster than deletes. Of course, the Fibonacci heaps are asymptotically
350 optimal (by the standard $\Omega(n\log n)$ lower bound on sorting by comparisons, see
351 for example \cite{clrs}), so the other data structures can improve only
352 multiplicative constants or offer an~easier implementation.
353
354 A~nice example is a~\df{$d$-regular heap} --- a~variant of the usual binary heap
355 in the form of a~complete $d$-regular tree. \<Insert>, \<Decrease> and other operations
356 involving bubbling the values up spend $\O(1)$ time at a~single level, so they run
357 in~$\O(\log_d n)$ time. \<Delete> and \<DeleteMin> require bubbling down, which incurs
358 comparison with all~$d$ sons at every level, so they spend $\O(d\log_d n)$.
359 With this structure, the time complexity of the whole algorithm
360 is $\O(nd\log_d n + m\log_d n)$, which suggests setting $d=m/n$, yielding $\O(m\log_{m/n}n)$.
361 This is still linear for graphs with density at~least~$n^{1+\varepsilon}$.
362
363 Another possibility is to use the 2-3-heaps \cite{takaoka:twothree} or Trinomial
364 heaps \cite{takaoka:trinomial}. Both have the same asymptotic complexity as Fibonacci
365 heaps (the latter even in the worst case, but it does not matter here) and their
366 authors claim faster implementation. For integer weights, we can use Thorup's priority
367 queues described in \cite{thorup:pqsssp} which have constant-time \<Insert> and \<Decrease>
368 and $\O(\log\log n)$ time \<DeleteMin>. (We will however omit the details since we will
369 show a~faster integer algorithm soon.)
370
371 \para
372 As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time
373 for sufficiently dense graphs. In some cases, it is useful to combine it with
374 another MST algorithm, which identifies a~part of the MST edges and contracts
375 the graph to increase its density. For example, we can perform several
376 iterations of the Contractive Bor\o{u}vka's algorithm and find the rest of the
377 MST by the Active Edge Jarn\'\i{}k's algorithm.
378
379 \algn{Mixed Bor\o{u}vka-Jarn\'\i{}k}
380 \algo
381 \algin A~graph~$G$ with an edge comparison oracle.
382 \:Run $\log\log n$ iterations of the Contractive Bor\o{u}vka's algorithm (\ref{contbor}),
383   getting a~MST~$T_1$.
384 \:Run the Active Edge Jarn\'\i{}k's algorithm (\ref{jarniktwo}) on the resulting
385   graph, getting a~MST~$T_2$.
386 \:Combine $T_1$ and~$T_2$ to~$T$ as in the Contraction lemma (\ref{contlemma}).
387 \algout Minimum spanning tree~$T$.
388 \endalgo
389
390 \thm
391 The Mixed Bor\o{u}vka-Jarn\'\i{}k algorithm finds the MST of the input graph in time $\O(m\log\log n)$.
392
393 \proof
394 Correctness follows from the Contraction lemma and from the proofs of correctness of the respective algorithms.
395 As~for time complexity: The first step takes $\O(m\log\log n)$ time
396 (by Lemma~\ref{contiter}) and it gradually contracts~$G$ to a~graph~$G'$ of size
397 $m'\le m$ and $n'\le n/\log n$. The second step then runs in time $\O(m'+n'\log n') = \O(m)$
398 and both trees can be combined in linear time, too.
399 \qed
400
401 \para
402 Actually, there is a~much better choice of the algorithms to combine: use the
403 Active Edge Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while.
404 A~good choice of the stopping condition is to place a~limit on the size of the heap.
405 We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
406 we conserve the current tree and start with a~different vertex and an~empty heap. When this
407 process runs out of vertices, it has identified a~sub-forest of the MST, so we can
408 contract the graph along the edges of~this forest and iterate.
409
410 \algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}
411 \algo
412 \algin A~graph~$G$ with an edge comparison oracle.
413 \:$T\=\emptyset$. \cmt{edges of the MST}
414 \:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
415 \:$m_0\=m$.
416 \:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
417 \::$F\=\emptyset$. \cmt{forest built in the current phase}
418 \::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
419 \::While there is a~vertex $v_0\not\in F$:
420 \:::Run the Active Edge Jarn\'\i{}k's algorithm (\ref{jarniktwo}) from~$v_0$, stop when:
421 \::::all vertices have been processed, or
422 \::::a~vertex of~$F$ has been added to the tree, or
423 \::::the heap has grown to more than~$t$ elements.
424 \:::Denote the resulting tree~$R$.
425 \:::$F\=F\cup R$.
426 \::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
427 \::Contract~$G$ along all edges of~$F$ and flatten it.
428 \algout Minimum spanning tree~$T$.
429 \endalgo
430
431 \nota
432 For analysis of the algorithm, let us denote the graph entering the $i$-th
433 phase by~$G_i$ and likewise with the other parameters. Let the trees from which
434 $F_i$~has been constructed be called $R_i^1, \ldots, R_i^{z_i}$. The
435 non-indexed $G$, $m$ and~$n$ will correspond to the graph given as~input.
436
437 \para
438 However the choice of the parameter~$t$ can seem mysterious, the following
439 lemma makes the reason clear:
440
441 \lemma\id{ijphase}%
442 The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$.
443
444 \proof
445 During the phase, the heap always contains at most~$t_i$ elements, so it takes
446 time~$\O(\log t_i)=\O(m/n_i)$ to delete an~element from the heap. The trees~$R_i^j$
447 are edge-disjoint, so there are at most~$n_i$ \<DeleteMin>'s over the course of the phase.
448 Each edge is considered at most twice (once per its endpoint), so the number
449 of the other heap operations is~$\O(m_i)$. Together, it equals $\O(m_i + n_i\log t_i) = \O(m_i+m) = \O(m)$.
450 \qed
451
452 \lemma
453 Unless the $i$-th phase is final, the forest~$F_i$ consists of at most $2m_i/t_i$ trees.
454
455 \proof
456 As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient
457 to establish that there are at least~$t_i$ edges incident with every such tree, including
458 connecting two vertices of the tree.
459
460 The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the possibilities
461 how the algorithm could have stopped growing the tree~$R_i^j$:
462 \itemize\ibull
463 \:the heap had more than~$t_i$ elements (step~10): since the each elements stored in the heap
464   corresponds to a~unique edges incident with~$R_i^j$, we have enough such edges;
465 \:the algorithm just added a~vertex of~$F_i$ to~$R_i^j$ (step~9): in this case, an~existing
466   tree of~$F_i$ is extended, so the number of edges incident with it cannot decrease;\foot{%
467   This is the place where we needed to count the interior edges as well.}
468 \:all vertices have been processed (step~8): this can happen only in the final phase.
469 \qeditem
470 \endlist
471
472 \thm\id{itjarthm}%
473 The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
474 $\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n \le m/n \}$.
475
476 \proof
477 Phases are finite and in every phase at least one edge is contracted, so the outer
478 loop is eventually terminated. The resulting subgraph~$T$ is equal to $\mst(G)$, because each $F_i$ is
479 a~subgraph of~$\mst(G_i)$ and the $F_i$'s are glued together according to the Contraction
480 lemma (\ref{contlemma}).
481
482 Let us bound the sizes of the graphs processed in the individual phases. As the vertices
483 of~$G_{i+1}$ correspond to the components of~$F_i$, by the previous lemma $n_{i+1}\le
484 2m_i/t_i$. Then $t_{i+1} = 2^{\lceil 2m/n_{i+1} \rceil} \ge 2^{2m/n_{i+1}} \ge 2^{2m/(2m_i/t_i)} = 2^{(m/m_i)\cdot t_i} \ge 2^{t_i}$,
485 therefore:
486 $$
487 \left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\rddots^{\scriptstyle m/n}}}} $}}\;\right\}
488 \,\hbox{a~tower of~$i$ exponentials.}
489 $$
490 As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time
491 there is enough space in the heap to process the whole graph. So~there are
492 at most~$\beta(m,n)$ phases and we already know (Lemma~\ref{ijphase}) that each
493 phase runs in linear time.
494 \qed
495
496 \cor
497 The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
498
499 \proof
500 $\beta(m,n) \le \beta(1,n) = \log^* n$.
501 \qed
502
503 \cor
504 When we use the Iterated Jarn\'\i{}k's algorithm on graphs with edge density
505 at least~$\log^{(k)} n$ for some $k\in{\bb N}^+$, it runs in time~$\O(km)$.
506
507 \proof
508 If $m/n \ge \log^{(k)} n$, then $\beta(m,n)\le k$.
509 \qed
510
511 \obs
512 The algorithm spends most of the time in phases which have small heaps. Once the
513 heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
514 to guarantee that at most~$k$ phases remain. This means that if we are able to
515 construct a~heap of size $\Omega(\log^{(k)} n)$ with constant time per operation,
516 we can get a~linear-time algorithm for MST. This is the case when the weights are
517 integers:
518
519 \thmn{MST for graphs with integer weights, Fredman and Willard \cite{fw:transdich}}\id{intmst}%
520 MST of a~graph with integer edge weights can be found in time $\O(m)$ on the Word-RAM.
521
522 \proof
523 We will combine the Iterated Jarn\'\i{}k's algorithm with the Q-heaps from section \ref{qheaps}.
524 We modify the first pass of the algorithm to choose $t=\log n$ and use the Q-heap tree instead
525 of the Fibonacci heap. From Theorem \ref{qh} and Remark \ref{qhtreerem} we know that the
526 operations on the Q-heap tree run in constant time, so the modified first phase takes time~$\O(m)$.
527 Following the analysis of the original algorithm in the proof of Theorem \ref{itjarthm} we obtain
528 $t_2\ge 2^{t_1} = 2^{\log n} = n$, so the algorithm stops after the second phase.\foot{%
529 Alternatively, we can use the Q-heaps directly with $k=\log^{1/4}n$ and then stop
530 after the third phase.}
531 \qed
532
533 \rem
534 Gabow et al.~\cite{gabow:mst} have shown how to speed up the Iterated Jarn\'\i{}k's algorithm to~$\O(m\log\beta(m,n))$.
535 They split the adjacency lists of the vertices to small buckets, keep each bucket
536 sorted and consider only the lightest edge in each bucket until it is removed.
537 The mechanics of the algorithm is complex and there is a~lot of technical details
538 which need careful handling, so we omit the description of this algorithm.
539
540 \FIXME{Reference to Chazelle.}
541
542 %--------------------------------------------------------------------------------
543
544 %\section{Verification of minimality}
545
546 %--------------------------------------------------------------------------------
547
548 \section{Special cases and related problems}
549
550 Finally, we will focus our attention on various special cases of the minimum
551 spanning tree problems, which frequently arise in practice.
552
553 \examplen{Graphs with sorted edges}
554 When the edges are already sorted by their weights, we can use the Kruskal's
555 algorithm to find the MST in time $\O(m\timesalpha(n))$ (Theorem \ref{kruskal}).
556 We however can do better: As the minimality of a~spanning tree depends only on the
557 order of weights and not on the actual values (Theorem \ref{mstthm}), we can
558 renumber the weights to $1, \ldots, m$ and find the MST using the Fredman-Willard
559 algorithm for integer weights. According to Theorem \ref{intmst} it runs in
560 time $\O(m)$ on the Word-RAM.
561
562 \examplen{Graphs with a~small number of distinct weights}
563 When the weights of edges are drawn from a~set of a~fixed size~$U$, we can
564 sort them in linear time and so reduce the problem to the previous case.
565 A~more practical way is to use the Jarn\'\i{}k's algorithm (\ref{jarnimpl}),
566 but replace the heap by an~array of $U$~buckets. As the number of buckets
567 is constant, we can find the minimum in constant time and hence the whole
568 algorithm runs in time $\O(m)$, even on the Pointer Machine. For large
569 values of~$U$, we can build a~binary search tree or the van Emde-Boas
570 tree (see Section \ref{ramdssect} and \cite{boas:vebt}) on the top of the buckets to bring the complexity
571 of finding the minimum down to $\O(\log U)$ or $\O(\log\log U)$ respectively.
572
573 \examplen{Graphs with floating-point weights}
574 A~common case of non-integer weights are rational numbers in floating-point (FP)
575 representation. Even in this case we will be able to find the MST in linear time.
576 The most common representation of binary FP numbers (as specified by the IEEE
577 standard 754-1985 \cite{ieee:binfp}) has the nice property that when the
578 bit strings encoding non-negative FP numbers are read as ordinary integers,
579 the order of these integers is the same as of the original FP numbers. We can
580 therefore once again replace the edge weights by integers and use the linear-time
581 integer algorithm. While the other FP representations (see \cite{dgoldberg:fp} for
582 an~overview) do not have this property, the corresponding integers can be adjusted
583 in $\O(1)$ time to the format we need. (More advanced tricks of this type been
584 employed by Thorup in \cite{thorup:floatint} to extend the integer algorithm
585 for single-source shortest paths to FP numbers.)
586
587 \examplen{Graphs with bounded degrees}
588 For graphs with vertex degrees bounded by a~constant~$\Delta$, the problem is either
589 trivial (if $\Delta<3$) or as hard as for arbitrary graphs. There is a~simple linear-time
590 transform of arbitrary graphs to graphs with maximum degree~3 which preserves the MST:
591
592 \lemman{Degree reduction}
593 For every graph~$G$ there exists a~graph~$G'$ with maximum degree at most~3 and
594 a~function $\pi: E(G)\rightarrow E(G')$ such that $\mst(G) = \pi^{-1}(\mst(G'))$.
595 The graph $G'$ and the embedding~$\pi$ can be constructed in time $\O(m)$.
596
597 \proof
598 We show how to eliminate a~single vertex~$v$ of degree $d>3$, the rest
599 will follow by induction.
600
601 Assume that $v$~has neighbors $w_1,\ldots,w_d$. We replace~$v$ and the edges~$vw_i$
602 by a~path $v_1v_2\ldots v_d$ and edges~$v_iw_i$. Each edge of the path will receive
603 weight smaller than all other weights, the other edges will inherit the weights
604 of the edges $vw_i$ they replace. The edges of the path will therefore lie in the
605 MST (this is obvious from the Kruskal's algorithm) and as~$G$ can be obtained from
606 the new~$G'$ by contracting the path, the rest follows from the Contraction lemma
607 (\ref{contlemma}).
608
609 This step can be carried out in time $\O(d)$. As it replaces a high-degree
610 vertex by vertices of degree~3, the procedure stops in at most~$n$ such
611 steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$ including the
612 time needed to find the high-degree vertices at the beginning.
613 \qed
614
615 \examplen{Euclidean MST}
616 The MST also has its analogies in the realm of geometric algorithms. Suppose
617 that we have $n$~points $x_1,\ldots,x_n$ in the plane and we want to find the
618 shortest system of segments connecting these points. If we want the segments to
619 touch only in the given points, this is equivalent to finding a~MST of the
620 complete graph on the vertices $V=\{v_1,\ldots,v_n\}$ with edge weights
621 equal to the Euclidean distances. Since the graph is dense, many of the MST
622 algorithms discussed run in linear time with the size of the graph, hence
623 in time $\O(n^2)$.
624
625 There is a~more efficient method based on the observation that the MST
626 is always a~subgraph of the Delaunay's tesselation for the given points
627 (this was first noted by Shamos and Hoey in~\cite{shamos:closest}). The
628 tesselation is a~planar graph, which guarantees that it has $\O(n)$ edges,
629 and it is a~dual graph to the Voronoi diagram of the points, which can
630 be constructed in time $\O(n\log n)$ using for example the Fortune's
631 algorithm \cite{fortune:voronoi}. We can therefore reduce the problem
632 to finding the MST of the tesselation for which $\O(n\log n)$ time
633 is more than enough.
634
635 This approach fails for non-Euclidean metrics, but in some cases
636 (in particular for the rectilinear metric) the $\O(n\log n)$ time
637 is also achievable by the algorithm of Zhou et al.~\cite{zhou:nodel}
638 based on the sweep-line technique and the Red rule. For other
639 variations on the geometric MST, see Eppstein's survey paper
640 \cite{eppstein:spanning}.
641
642 \examplen{Steiner trees}
643 The constraint that the segments in the previous example are allowed to touch
644 each other only in the given points looks artificial and it is is uncommon in
645 practical applications (including the application on electrical transmission
646 lines originally studied by Bor\o{u}vka). If we lift this restriction, we get
647 the problem known under the name Steiner tree.\foot{It is named after the Swiss mathematician
648 Jacob Steiner who studied a~special case of this problem in the 19th century.}
649 We can also define it in terms of graphs:
650
651 \defn A~\df{Steiner tree} of a~weighted graph~$(G,w)$ with a~set~$M\subseteq V$
652 of \df{mandatory notes} is a~tree~$T\subseteq G$ which contains all the mandatory
653 vertices and its weight is minimum possible.
654
655 Finding the Steiner tree has been proven to be NP-hard by Garey and
656 Johnson \cite{garey:steiner,garey:rectisteiner} in both the graph version
657 (even for weights $\{1,2\}$) and in the planar version with Euclidean or rectilinear
658 metric. There is a~polynomial approximation algorithm with ratio $5/3$ for
659 graphs due to Pr\"omel and Steger \cite{proemel:steiner} and a~polynomial-time
660 approximation scheme for the Euclidean Steiner tree in an~arbitrary dimension
661 by Arora \cite{arora:tspapx}.
662
663 \examplen{Approximating the weight of the MST}
664 Sometimes we are not interested in the actual edges forming the MST and only
665 the weight matters. If we are willing to put up with a~randomized approximation,
666 we can even achieve sub-linear complexity. Chazelle et al.~\cite{chazelle:mstapprox}
667 have shown an~algorithm which, given $0 < \varepsilon < 1/2$, approximates
668 the weight of the MST of a~graph with average degree~$d$ and edge weights from the set
669 $\{1,\ldots,w\}$ in time $\O(dw\varepsilon^{-2}\cdot\log(dw/\varepsilon))$,
670 producing a~weight which has relative error at most~$\varepsilon$ with probability
671 at least $3/4$. They have also proven an~almost matching lower bound $\Omega(dw\varepsilon^{-2})$.
672
673 For the $d$-dimensional Euclidean case, there is a~randomized approximation
674 algorithm by Czumaj et al.~\cite{czumaj:euclidean} which with high probability
675 produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\sqrt{n}\cdot \poly(1/\varepsilon))$\foot{%
676 $\widetilde\O(f(n)) = \O(f(n)\cdot\log^{\O(1)} f(n))$ and $\poly(n)=n^{\O(1)}$.}
677 queries to a~data structure containing the points. The data structure is expected
678 to answer orthogonal range queries and cone approximate nearest neighbor queries.
679 There is also $\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation
680 algorithm for MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}.
681 (This is still sub-linear since the corresponding graph has roughly $n^2$ edges.)
682
683 \endpart