5 \chapter{Advanced MST Algorithms}
7 \section{Minor-closed graph classes}\id{minorclosed}%
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.
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}).
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$.
25 Non-trivial minor-closed classes include:
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.
34 Many of the nice structural properties of planar graphs extend to
35 minor-closed classes, too (see \cite{diestel:gt} for a~nice overview
36 of this theory). The most important property is probably the characterization
37 of such classes in terms of their forbidden minors.
40 For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class
41 of graphs which do not contain any of the graphs in~$\cal H$ as a~minor.
42 We will call $\cal H$ the set of \df{forbidden (or excluded) minors} for this class.
43 We will often abbreviate $\Forb(\{M_1,\ldots,M_n\})$ to $\Forb(M_1,\ldots,M_n)$.
46 For every~${\cal H}\ne\emptyset$, the class $\Forb({\cal H})$ is non-trivial
47 and closed on minors. This works in the opposite direction as well: for every
48 minor-closed class~$\cal C$ there is a~class $\cal H$ such that ${\cal C}=\Forb({\cal H})$.
49 One such~$\cal H$ is the complement of~$\cal C$, but smaller ones can be found, too.
50 For example, the planar graphs can be equivalently described as the class $\Forb(K_5, K_{3,3})$
51 --- this follows from the Kuratowski's theorem (the theorem speaks of forbidden
52 subdivisions, but while in general this is not the same as forbidden minors, it
53 is for $K_5$ and $K_{3,3}$). The celebrated theorem by Robertson and Seymour
54 guarantees that we can always find a~finite set of forbidden minors.
56 \thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
57 For every non-trivial minor-closed graph class~$\cal C$ there exists
58 a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$.
61 This theorem has been proven in a~long series of papers on graph minors
62 culminating with~\cite{rs:wagner}. See this paper and follow the references
63 to the previous articles in the series.
67 For analysis of the contractive algorithm,
68 we will make use of another important property --- the bounded density of
69 minor-closed classes. The connection between minors and density dates back to
70 Mader in the 1960's and it can be proven without use of the Robertson-Seymour
74 Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$
75 to be the infimum of all~$\varrho$'s such that $m(G) \le \varrho\cdot n(G)$
76 holds for every $G\in\cal C$.
78 \thmn{Mader \cite{mader:dens}}
79 For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
80 of average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph.
83 (See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.)
85 Let us fix~$k$ and prove by induction on~$m$ that every graph of average
86 degree at least~$2^m$ contains a~subdivision of some graph with $k$~vertices
87 and ${k\choose 2}\ge m\ge k$~edges. For $m={k\choose 2}$ the theorem follows
88 as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$.
90 The base case $m=k$: Let us observe that when the average degree
91 is~$a$, removing any vertex of degree less than~$a/2$ does not decrease the
92 average degree. A~graph with $a\ge 2^k$ therefore has a~subgraph
93 with minimum degree $\delta\ge a/2=2^{k-1}$. Such subgraph contains
94 a~cycle on more than~$\delta$ vertices, in other words a~subdivision of
97 Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and
98 assume that the theorem already holds for $m-1$. Without loss of generality,
99 $G$~is connected. Consider a~maximal set $U\subseteq V$ such that the subgraph $G[U]$
100 induced by~$U$ is connected and the graph $G.U$ ($G$~with $U$~contracted to
101 a~single vertex) has average degree at least~$2^m$ (such~$U$ exists, because
102 $G=G.U$ whenever $\vert U\vert=1$). Now consider the subgraph~$H$ induced
103 in~$G$ by the neighbors of~$U$. Every $v\in V(H)$ must have $\deg_H(v) \ge 2^{m-1}$,
104 as otherwise we can add this vertex to~$U$, contradicting its
105 maximality. By the induction hypothesis, $H$ contains a~subdivision of some
106 graph~$R$ with $r$~vertices and $m-1$ edges. Any two non-adjacent vertices
107 of~$R$ can be connected in the subdivision by a~path lying entirely in~$G[U]$,
108 which reveals a~subdivision of a~graph with $m$~edges. \qed
110 \thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
111 Every non-trivial minor-closed class of graphs has finite edge density.
114 Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$.
115 As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(K_x)$, so
116 $\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the
117 theorem for classes excluding a~single complete graph~$K_x$.
119 We will show that $\varrho({\cal C})\le 2h(x)$, where $h$~is the function
120 from the previous theorem. If any $G\in{\cal C}$ had more than $2h(x)\cdot n(G)$
121 edges, its average degree would be at least~$h(x)$, so by the previous theorem
122 $G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor.
126 Minor-closed classes share many other interesting properties, as shown for
127 example by Theorem 6.1 of \cite{nesetril:minors}.
129 \thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}%
130 For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
131 algorithm (\ref{contbor}) finds the MST of any graph of this class in time
132 $\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
135 Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered
136 by the algorithm at the beginning of the $i$-th iteration by~$G_i$ and its number of vertices
137 and edges by $n_i$ and $m_i$ respectively. Again the $i$-th phase runs in time $\O(m_i)$
138 and $n_i \le n/2^i$, so it remains to show a linear bound for the $m_i$'s.
140 Since each $G_i$ is produced from~$G_{i-1}$ by a sequence of edge contractions,
141 all $G_i$'s are minors of~$G$.\foot{Technically, these are multigraph contractions,
142 but followed by flattening, so they are equivalent to contractions on simple graphs.}
143 So they also belong to~$\cal C$ and by the previous theorem $m_i\le \varrho({\cal C})\cdot n_i$.
147 The contractive algorithm uses ``batch processing'' to perform many contractions
148 in a single step. It is also possible to perform contractions one edge at a~time,
149 batching only the flattenings. A~contraction of an edge~$uv$ can be done
150 in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back
151 with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small
152 degrees. The following lemma shows that this is always the case in minor-closed
155 \lemman{Low-degree vertices}\id{lowdeg}%
156 Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph
157 with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$.
160 Assume the contrary: Let there be at least $n/2$ vertices with degree
161 greater than~$4\varrho$. Then $\sum_v \deg(v) > n/2
162 \cdot 4\varrho = 2\varrho n$, which is in contradiction with the number
163 of edges being at most $\varrho n$.
167 The proof can be also viewed
168 probabilistically: let $X$ be the degree of a vertex of~$G$ chosen uniformly at
169 random. Then ${\bb E}X \le 2\varrho$, hence by the Markov's inequality
170 ${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have
171 $\deg(v)\le 4\varrho$.
173 \algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}%
175 \algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
177 \:$\ell(e)\=e$ for all edges~$e$.
179 \::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
180 \:::Select the lightest edge~$e$ incident with~$v$.
181 \:::Contract~$G$ along~$e$.
182 \:::$T\=T + \ell(e)$.
183 \::Flatten $G$, removing parallel edges and loops.
184 \algout Minimum spanning tree~$T$.
188 When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the
189 Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$
190 finds the MST of any graph from this class in time $\O(n)$. (The constant
191 in the~$\O$ depends on~the class.)
194 Let us denote by $G_i$, $n_i$ and $m_i$ the graph considered by the
195 algorithm at the beginning of the $i$-th iteration of the outer loop,
196 and the number of its vertices and edges respectively. As in the proof
197 of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s
198 are minors of the graph~$G$ given as the input.
200 For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
201 guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
202 have degree at most~$t$. Each selected edge removes one such vertex and
203 possibly increases the degree of another, so at least $n_i/4$ edges get selected.
204 Hence $n_i\le 3/4\cdot n_{i-1}$ and therefore $n_i\le n\cdot (3/4)^i$ and the
205 algorithm terminates after $\O(\log n)$ iterations.
207 Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
208 the trivial cut $\delta(v)$ (see the Blue Rule in \ref{rbma}).
209 The steps 6 and~7 therefore correspond to the operation
210 described by the Lemma on contraction of MST edges (\ref{contlemma}) and when
211 the algorithm stops, $T$~is indeed the minimum spanning tree.
213 It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have
214 $m_i\le \varrho n_i \le \varrho n/2^i$.
215 We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
216 Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
217 over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$.
218 Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting
219 Bor\o{u}vka's Algorithm (see \ref{contiter}).
221 The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
225 For planar graphs, we can get a sharper version of the low-degree lemma,
226 showing that the algorithm works with $t=8$ as well (we had $t=12$ as
227 $\varrho=3$). While this does not change the asymptotic time complexity
228 of the algorithm, the constant-factor speedup can still delight the hearts of
231 \lemman{Low-degree vertices in planar graphs}%
232 Let $G$ be a planar graph with $n$~vertices. Then at least $n/2$ vertices of~$v$
233 have degree at most~8.
236 It suffices to show that the lemma holds for triangulations (if there
237 are any edges missing, the situation can only get better) with at
238 least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$.
239 The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
240 so by the same argument as in the proof of the general lemma, for at least $n/2$
241 vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$.
245 The constant~8 in the previous lemma is the best we can have.
246 Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them
247 lie on the outer face and have degrees at most~6, the remaining $n-\O(k)$ interior
248 vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$,
249 ignoring terms of order $\O(k)$. All interior triangles can be properly colored with
250 two colors, black and white. Now add a~new vertex inside each white face and connect
251 it to all three vertices on the boundary of that face. This adds $f/2 \approx n$
252 vertices of degree~3 and it increases the degrees of the original $\approx n$ interior
253 vertices to~9, therefore about a half of the vertices of the new planar graph
256 \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
259 The observation in~Theorem~\ref{mstmcc} was also made by Gustedt in~\cite{gustedt:parallel},
260 who studied a~parallel version of the contractive Bor\o{u}vka's algorithm applied
261 to minor-closed classes.
263 %--------------------------------------------------------------------------------
265 \section{Using Fibonacci heaps}
268 We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
269 Fredman and Tarjan have shown a~faster implementation in~\cite{ft:fibonacci}
270 using their Fibonacci heaps. In this section, we convey their results and we
271 show several interesting consequences.
273 The previous implementation of the algorithm used a binary heap to store all edges
274 separating the current tree~$T$ from the rest of the graph, i.e., edges of the cut~$\delta(T)$.
275 Instead of that, we will remember the vertices adjacent to~$T$ and for each such vertex~$v$ we
276 will maintain the lightest edge~$uv$ such that $u$~lies in~$T$. We will call these edges \df{active edges}
277 and keep them in a~Fibonacci heap, ordered by weight.
279 When we want to extend~$T$ by the lightest edge of~$\delta(T)$, it is sufficient to
280 find the lightest active edge~$uv$ and add this edge to~$T$ together with the new vertex~$v$.
281 Then we have to update the active edges as follows. The edge~$uv$ has just ceased to
282 be active. We scan all neighbors~$w$ of the vertex~$v$. When $w$~is in~$T$, no action
283 is needed. If $w$~is outside~$T$ and it was not adjacent to~$T$ (there is no active edge
284 remembered for it so far), we set the edge~$vw$ as active. Otherwise we check the existing
285 active edge for~$w$ and replace it by~$vw$ if the new edge is lighter.
287 The following algorithm shows how these operations translate to insertions, decreases
288 and deletions on the heap.
290 \algn{Active Edge Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}%
292 \algin A~graph~$G$ with an edge comparison oracle.
293 \:$v_0\=$ an~arbitrary vertex of~$G$.
294 \:$T\=$ a tree containing just the vertex~$v_0$.
295 \:$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.
296 \:$A\=$ a~mapping of vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
297 \:\<Insert> all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly.
298 \:While $H$ is not empty:
299 \::$(u,v)\=\<DeleteMin>(H)$.
301 \::For all edges $vw$ such that $w\not\in T$:
302 \:::If there exists an~active edge~$A(w)$:
303 \::::If $vw$ is lighter than~$A(w)$, \<Decrease> $A(w)$ to~$(v,w)$ in~$H$.
304 \:::If there is no such edge, then \<Insert> $(v,w)$ to~$H$ and set~$A(w)$.
305 \algout Minimum spanning tree~$T$.
309 To analyze the time complexity of this algorithm, we will use the standard
310 theorem on~complexity of the Fibonacci heap:
312 \thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations
313 with the indicated amortized time complexities:
315 \:\<Insert> (insertion of a~new element) in $\O(1)$,
316 \:\<Decrease> (decreasing value of an~existing element) in $\O(1)$,
317 \:\<Merge> (merging of two heaps into one) in $\O(1)$,
318 \:\<DeleteMin> (deletion of the minimal element) in $\O(\log n)$,
319 \:\<Delete> (deletion of an~arbitrary element) in $\O(\log n)$,
321 \>where $n$ is the number of elements present in the heap at the time of
325 See Fredman and Tarjan \cite{ft:fibonacci} for both the description of the Fibonacci
326 heap and the proof of this theorem.
330 Algorithm~\ref{jarniktwo} with the Fibonacci heap finds the MST of the input graph in time~$\O(m+n\log n)$.
333 The algorithm always stops, because every edge enters the heap~$H$ at most once.
334 As it selects exactly the same edges as the original Jarn\'\i{}k's algorithm,
335 it gives the correct answer.
337 The time complexity is $\O(m)$ plus the cost of the heap operations. The algorithm
338 performs at most one \<Insert> or \<Decrease> per edge and exactly one \<DeleteMin>
339 per vertex. There are at most $n$ elements in the heap at any given time,
340 thus by the previous theorem the operations take $\O(m+n\log n)$ time in total.
344 For graphs with edge density at least $\log n$, this algorithm runs in linear time.
347 We can consider using other kinds of heaps which have the property that inserts
348 and decreases are faster than deletes. Of course, the Fibonacci heaps are asymptotically
349 optimal (by the standard $\Omega(n\log n)$ lower bound on sorting by comparisons, see
350 for example \cite{clrs}), so the other data structures can improve only
351 multiplicative constants or offer an~easier implementation.
353 A~nice example is a~\df{$d$-regular heap} --- a~variant of the usual binary heap
354 in the form of a~complete $d$-regular tree. \<Insert>, \<Decrease> and other operations
355 involving bubbling the values up spend $\O(1)$ time at a~single level, so they run
356 in~$\O(\log_d n)$ time. \<Delete> and \<DeleteMin> require bubbling down, which incurs
357 comparison with all~$d$ sons at every level, so they spend $\O(d\log_d n)$.
358 With this structure, the time complexity of the whole algorithm
359 is $\O(nd\log_d n + m\log_d n)$, which suggests setting $d=m/n$, yielding $\O(m\log_{m/n}n)$.
360 This is still linear for graphs with density at~least~$n^{1+\varepsilon}$.
362 Another possibility is to use the 2-3-heaps \cite{takaoka:twothree} or Trinomial
363 heaps \cite{takaoka:trinomial}. Both have the same asymptotic complexity as Fibonacci
364 heaps (the latter even in the worst case, but it does not matter here) and their
365 authors claim faster implementation.
367 \FIXME{Mention Thorup's Fibonacci-like heaps for integers?}
370 As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time
371 for sufficiently dense graphs. In some cases, it is useful to combine it with
372 another MST algorithm, which identifies a~part of the MST edges and contracts
373 the graph to increase its density. For example, we can perform several
374 iterations of the Contractive Bor\o{u}vka's algorithm and find the rest of the
375 MST by the Active Edge Jarn\'\i{}k's algorithm.
377 \algn{Mixed Bor\o{u}vka-Jarn\'\i{}k}
379 \algin A~graph~$G$ with an edge comparison oracle.
380 \:Run $\log\log n$ iterations of the Contractive Bor\o{u}vka's algorithm (\ref{contbor}),
382 \:Run the Active Edge Jarn\'\i{}k's algorithm (\ref{jarniktwo}) on the resulting
383 graph, getting a~MST~$T_2$.
384 \:Combine $T_1$ and~$T_2$ to~$T$ as in the Contraction lemma (\ref{contlemma}).
385 \algout Minimum spanning tree~$T$.
389 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 Correctness follows from the Contraction lemma and from the proofs of correctness of the respective algorithms.
393 As~for time complexity: The first step takes $\O(m\log\log n)$ time
394 (by Lemma~\ref{contiter}) and it gradually contracts~$G$ to a~graph~$G'$ of size
395 $m'\le m$ and $n'\le n/\log n$. The second step then runs in time $\O(m'+n'\log n') = \O(m)$
396 and both trees can be combined in linear time, too.
400 Actually, there is a~much better choice of the algorithms to combine: use the
401 Active Edge Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while.
402 A~good choice of the stopping condition is to place a~limit on the size of the heap.
403 We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
404 we conserve the current tree and start with a~different vertex and an~empty heap. When this
405 process runs out of vertices, it has identified a~sub-forest of the MST, so we can
406 contract the graph along the edges of~this forest and iterate.
408 \algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}
410 \algin A~graph~$G$ with an edge comparison oracle.
411 \:$T\=\emptyset$. \cmt{edges of the MST}
412 \:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
414 \:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
415 \::$F\=\emptyset$. \cmt{forest built in the current phase}
416 \::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
417 \::While there is a~vertex $v_0\not\in F$:
418 \:::Run the Active Edge Jarn\'\i{}k's algorithm (\ref{jarniktwo}) from~$v_0$, stop when:
419 \::::all vertices have been processed, or
420 \::::a~vertex of~$F$ has been added to the tree, or
421 \::::the heap has grown to more than~$t$ elements.
422 \:::Denote the resulting tree~$R$.
424 \::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
425 \::Contract~$G$ along all edges of~$F$ and flatten it.
426 \algout Minimum spanning tree~$T$.
430 For analysis of the algorithm, let us denote the graph entering the $i$-th
431 phase by~$G_i$ and likewise with the other parameters. Let the trees from which
432 $F_i$~has been constructed be called $R_i^1, \ldots, R_i^{z_i}$. The
433 non-indexed $G$, $m$ and~$n$ will correspond to the graph given as~input.
436 However the choice of the parameter~$t$ can seem mysterious, the following
437 lemma makes the reason clear:
440 The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$.
443 During the phase, the heap always contains at most~$t_i$ elements, so it takes
444 time~$\O(\log t_i)=\O(m/n_i)$ to delete an~element from the heap. The trees~$R_i^j$
445 are edge-disjoint, so there are at most~$n_i$ \<DeleteMin>'s over the course of the phase.
446 Each edge is considered at most twice (once per its endpoint), so the number
447 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)$.
451 Unless the $i$-th phase is final, the forest~$F_i$ consists of at most $2m_i/t_i$ trees.
454 As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient
455 to establish that there are at least~$t_i$ edges incident with every such tree, including
456 connecting two vertices of the tree.
458 The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the possibilities
459 how the algorithm could have stopped growing the tree~$R_i^j$:
461 \:the heap had more than~$t_i$ elements (step~10): since the each elements stored in the heap
462 corresponds to a~unique edges incident with~$R_i^j$, we have enough such edges;
463 \:the algorithm just added a~vertex of~$F_i$ to~$R_i^j$ (step~9): in this case, an~existing
464 tree of~$F_i$ is extended, so the number of edges incident with it cannot decrease;\foot{%
465 This is the place where we needed to count the interior edges as well.}
466 \:all vertices have been processed (step~8): this can happen only in the final phase.
471 The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
472 $\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n \le m/n \}$.
475 Phases are finite and in every phase at least one edge is contracted, so the outer
476 loop is eventually terminated. The resulting subgraph~$T$ is equal to $\mst(G)$, because each $F_i$ is
477 a~subgraph of~$\mst(G_i)$ and the $F_i$'s are glued together according to the Contraction
478 lemma (\ref{contlemma}).
480 Let us bound the sizes of the graphs processed in the individual phases. As the vertices
481 of~$G_{i+1}$ correspond to the components of~$F_i$, by the previous lemma $n_{i+1}\le
482 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 \left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\rddots^{\scriptstyle m/n}}}} $}}\;\right\}
486 \,\hbox{a~tower of~$i$ exponentials.}
488 As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time
489 there is enough space in the heap to process the whole graph. So~there are
490 at most~$\beta(m,n)$ phases and we already know (Lemma~\ref{ijphase}) that each
491 phase runs in linear time.
495 The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
498 $\beta(m,n) \le \beta(1,n) = \log^* n$.
502 When we use the Iterated Jarn\'\i{}k's algorithm on graphs with edge density
503 at least~$\log^{(k)} n$ for some $k\in{\bb N}^+$, it runs in time~$\O(km)$.
506 If $m/n \ge \log^{(k)} n$, then $\beta(m,n)\le k$.
510 Gabow et al.~\cite{gabow:mst} have shown how to speed this algorithm up to~$\O(m\log\beta(m,n))$.
511 They split the adjacency lists of the vertices to small buckets, keep each bucket
512 sorted and consider only the lightest edge in each bucket until it is removed.
513 The mechanics of the algorithm is complex and there is a~lot of technical details
514 which need careful handling, so we omit the description of this algorithm.
516 \FIXME{Reference to Chazelle.}
518 \FIXME{Reference to Q-Heaps.}
520 %--------------------------------------------------------------------------------
522 %\section{Verification of minimality}