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{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.
41 For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class
42 of graphs that 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)$.
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.
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})$.
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.
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
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$.
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.
84 (See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.)
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$.
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
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
111 \thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
112 Every non-trivial minor-closed class of graphs has finite edge density.
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$.
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.
127 Minor-closed classes share many other interesting properties, as shown for
128 example by Theorem 6.1 of \cite{nesetril:minors}.
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.)
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.
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$.
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
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$.
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$.
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$.
174 \algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}%
176 \algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
178 \:$\ell(e)\=e$ for all edges~$e$.
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$.
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.)
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.
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.
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.
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}).
222 The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
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
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.
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$.
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
257 \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
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.
264 %--------------------------------------------------------------------------------
266 \section{Using Fibonacci heaps}
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.
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.
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.
288 The following algorithm shows how these operations translate to insertions, decreases
289 and deletions on the heap.
291 \algn{Active Edge Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}%
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)$.
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$.
310 To analyze the time complexity of this algorithm, we will use the standard
311 theorem on~complexity of the Fibonacci heap:
313 \thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations
314 with the indicated amortized time complexities:
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)$,
322 \>where $n$ is the number of elements present in the heap at the time of
326 See Fredman and Tarjan \cite{ft:fibonacci} for both the description of the Fibonacci
327 heap and the proof of this theorem.
331 Algorithm~\ref{jarniktwo} with the Fibonacci heap finds the MST of the input graph in time~$\O(m+n\log n)$.
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.
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.
345 For graphs with edge density at least $\log n$, this algorithm runs in linear time.
348 We can consider using other kinds of heaps that 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.
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}$.
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.)
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.
379 \algn{Mixed Bor\o{u}vka-Jarn\'\i{}k}
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}),
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$.
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)$.
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.
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.
410 \algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}
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}
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$.
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$.
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.
438 However the choice of the parameter~$t$ can seem mysterious, the following
439 lemma makes the reason clear:
442 The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$.
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)$.
453 Unless the $i$-th phase is final, the forest~$F_i$ consists of at most $2m_i/t_i$ trees.
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.
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$:
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.
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 \}$.
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}).
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}$,
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.}
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.
497 The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
500 $\beta(m,n) \le \beta(1,n) = \log^* n$.
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)$.
508 If $m/n \ge \log^{(k)} n$, then $\beta(m,n)\le k$.
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
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.
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.}
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.
540 \FIXME{Reference to Chazelle.}
542 %--------------------------------------------------------------------------------
544 \section{Verification of minimality}
546 Now we will turn our attention to a~slightly different problem: given a~spanning
547 tree, how to verify that it is minimum? We will show that this can be achieved
548 in linear time and it will serve as a~basis for a~randomized linear-time
549 MST algorithm in Section~\ref{randmst}.
551 MST verification has been studied by Koml\'os \cite{komlos:verify}, who has
552 proven that $\O(m)$ edge comparisons are sufficient, but his algorithm needed
553 superlinear time to find the edges to compare. Dixon, Rauch and Tarjan
554 have later shown in \cite{dixon:verify} that the overhead can be reduced
555 to linear time on the RAM using preprocessing and table lookup on small
556 subtrees. Later, King has given a~simpler algorithm in \cite{king:verifytwo}.
558 In this section, we will follow Koml\'os's steps and study the comparisons
559 needed, saving the actual efficient implementation for later.
562 To verify that a~spanning~$T$ is minimum, it is sufficient to check that all
563 edges outside~$T$ are $T$-heavy (by Theorem \ref{mstthm}). In fact, we will be
564 able to find all $T$-light edges efficiently. For each edge $uv\in E\setminus T$,
565 we will find the heaviest edge of the tree path $T[u,v]$ and compare its weight
566 to $w(uv)$. It is therefore sufficient to solve the following problem:
569 Given a~weighted tree~$T$ and a~set of \df{query paths} $Q \subseteq \{ T[u,v] ; u,v\in V(T) \}$
570 specified by their endpoints, find the heaviest edge (\df{peak}) for every path in~$Q$.
573 Finding the peaks can be burdensome if the tree~$T$ is degenerated,
574 so we will first reduce it to the same problem on a~balanced tree. We run
575 the Bor\o{u}vka's algorithm on~$T$, which certainly produces $T$ itself, and we
576 record the order in which the subtrees have been merged in another tree~$B(T)$.
577 The peak queries on~$T$ can be then easily translated to peak queries on~$B(T)$.
580 For a~weighted tree~$T$ we define its \df{Bor\o{u}vka tree} $B(T)$ as a~rooted tree which records
581 the execution of the Bor\o{u}vka's algorithm run on~$T$. The leaves of $B(T)$
582 are all the vertices of~$T$, an~internal vertex~$v$ at level~$i$ from the bottom
583 corresponds to a~component tree~$C(v)$ formed in the $i$-th phase of the algorithm. When
584 a~tree $C(v)$ selects an adjacent edge~$e$ and gets merged with some other trees to form
585 a~component $C(u)$, we add an~edge $uv$ to~$B(T)$ and set its weight to $w(e)$.
587 \figure{bortree.eps}{\epsfxsize}{An octipede and its Bor\o{u}vka tree}
590 As the algorithm finishes with a~single component in the last phase, the Bor\o{u}vka tree
591 is really a~tree. All its leaves are on the same level and each internal vertex has
592 at least two sons. Such trees will be called \df{complete branching trees.}
595 For every tree~$T$ and every pair of its vertices $x,y\in V(T)$, the peak
596 of the path $T[x,y]$ has the same weight as the peak of~the path $B(T)[x,y]$.
599 Let us denote the path $T[x,y]$ by~$P$ and its heaviest edge by~$h=ab$. Similarly,
600 let us use $P'$ for $B(T)[x,y]$ and $h'$ for the heaviest edge of~$P'$.
602 We will first prove that~$h$ has its counterpart of the same weight in~$P'$,
603 so $w(h') \ge w(h)$. Consider the lowest vertex $u$ of~$B(T)$ such that the
604 component $C(u)$ contains both $a$ and~$b$, and consider the sons $v_a$ and $v_b$ of~$u$
605 for which $a\in C(v_a)$ and $b\in C(v_b)$. As the edge~$h$ must have been
606 selected by at least one of these components, we assume without loss of generality that
607 it was $C(v_a)$, and hence we have $w(uv_a)=w(h)$. We will show that the
608 edge~$uv_a$ lies in~$P'$, because exactly one of the endpoints of~$h$ lies
609 in~$C(v_a)$. Both endpoints cannot lie there, since it would imply that $C(v_a)$,
610 being connected, contains the whole path~$P$, including~$h$. On the other hand,
611 if $C(v_a)$ contained neither~$x$ nor~$y$, it would have to be incident with
612 another edge of~$P$ different from~$h$, so this lighter edge would be selected
615 In the other direction: for any edge~$uv\in P'$, the tree~$C(v)$ is incident
616 with at least one edge of~$P$, so the selected edge must be lighter or equal
617 to this edge and hence also to~$h$.
621 We will simplify the problem even further: For an~arbitrary tree~$T$, we split each
622 query path $T[x,y]$ to two half-paths $T[x,a]$ and $T[a,y]$ where~$a$ is the
623 \df{lowest common ancestor} of~$x$ and~$y$ in~$T$. It is therefore sufficient to
624 consider only paths that connect a~vertex with one of its ancestors.
626 When we combine the two transforms, we get:
628 \lemma\id{verbranch}%
629 For each tree~$T$ on $n$~vertices and a~set~$Q$ of $q$~query paths on~$T$, it is possible
630 to find a~complete branching tree~$T'$, together with a~set~$Q'$ of paths on~$T'$,
631 such that the weights of the heaviest edges of the paths in~$Q$ can be deduced from
632 the same of the paths in~$Q'$. The tree $T'$ has at most $2n$ vertices and $\O(\log n)$
633 levels. The set~$Q'$ contains at most~$2q$ paths and each of them connects a~vertex of~$T'$
634 with one of its ancestors. The construction of~$T'$ involves $\O(n)$ comparisons
635 and the transformation of the answers takes $\O(q)$ comparisons.
638 The tree~$T'$ will be the Bor\o{u}vka tree for~$T$, obtained by running the
639 contractive version of the Bor\o{u}vka's algorithm (Algorithm \ref{contbor})
640 on~$T$. The algorithm runs in linear time, for example because trees are planar
641 (Theorem \ref{planarbor}). We therefore spend $\O(n)$ comparisons in it.
643 As~$T'$ has~$n$ leaves and it is a~complete branching tree, it has at most~$n$ internal vertices,
644 so~$n(T')\le 2n$ as promised. Since the number of passes of the Bor\o{u}vka's
645 algorithm is $\O(\log n)$, the depth of the Bor\o{u}vka tree must be logarithmic as well.
647 For each query path $T[x,y]$ we find the lowest common ancestor of~$x$ and~$y$
648 and split the path by the two half-paths. This produces a~set~$Q'$ of at most~$2q$ half-paths.
649 The peak of every original query path is then the heavier of the peaks of its halves.
653 We will now describe a~simple variant of the depth-first search which finds the
654 peaks of all query paths of the transformed problem. As we promised,
655 we will take care of the number of comparisons only, as long as all other operations
656 are well-defined and they can be performed in polynomial time.
659 For every edge~$e=uv$, we consider the set $Q_e$ of all query paths containing~$e$.
660 The vertex of a~path, which is closer to the root, will be called its \df{top,}
661 the other vertex its \df{bottom.}
662 We define arrays $T_e$ and~$P_e$ as follows: $T_e$ contains
663 the tops of the paths in~$Q_e$ in order of their increasing depth (we
664 will call them \df{active tops} and each of them will be stored exactly once). For
665 each active top~$t=T_e[i]$, we define $P_e[i]$ as the peak of the path $T[v,t]$.
668 As for every~$i$ the path $T[v,T_e[i+1]]$ is contained within $T[v,T_e[i]]$,
669 the edges of~$P_e$ must have non-increasing weights, that is $w(P_e[i+1]) \le
672 \alg $\<FindPeaks>(u,p,T_p,P_p)$ --- process all queries in the subtree rooted
673 at~$u$ entered from its parent via an~edge~$p$.
677 \:Process all query paths whose bottom is~$u$ and record their peaks.
678 This is accomplished by finding the index~$i$ of each path's top in~$T_p$ and reading
679 the desired edge from~$P_p[i]$.
681 \:For every son~$v$ of~$u$, process the edge $e=uv$:
683 \::Construct the array of tops~$T_e$ for the edge~$e$: Start with~$T_p$, remove
684 the tops of the paths that do not contain~$e$ and add the vertex~$u$ itself
685 if there is a~query path which has~$u$ as its top and which has bottom somewhere
686 in the subtree rooted at~$v$.
688 \::Prepare the array of the peaks~$P_e$: Start with~$P_p$, remove the entries
689 corresponding to the tops that are no longer active. If $u$ became an~active
690 top, append~$e$ to the array.
693 Since the paths leading to all active tops have been extended by the
694 edge~$e$, compare $w(e)$ with weights of the edges recorded in~$P_e$ and replace
695 those edges which are lighter by~$e$.
696 Since $P_p$ was sorted, we can use binary search
697 to locate the boundary between lighter and heavier edges in~$P_e$.
699 \::Recurse on~$v$: call $\<FindPeaks>(v,e,T_e,P_e)$.
702 \>As we need a~parent edge to start the recursion, we add an~imaginary parent
703 edge~$p_0$ of the root vertex~$r$, for which no queries are defined. We can
704 therefore start with $\<FindPeaks>(r,p_0,\emptyset,\emptyset)$.
706 Let us account for the comparisons:
708 \lemma\id{vercompares}%
709 When the procedure \<FindPeaks> is called on the transformed problem, it
710 performs $\O(n+q)$ comparisons, where $n$ is the size of the tree and
711 $q$ is the number of query paths.
714 We will calculate the number of comparisons~$c_i$ performed when processing the edges
715 going from the $(i+1)$-th to the $i$-th level of the tree.
716 The levels are numbered from the bottom, so leaves are at level~0 and the root
717 is at level $\ell\le \lceil \log_2 n\rceil$. There are $n_i\le n/2^i$ vertices
718 at the $i$-th level, so we consider exactly $n_i$ edges. To avoid taking a~logarithm
719 of zero, we define $\vert T_e\vert=1$ for $T_e=\emptyset$.
720 \def\eqalign#1{\null\,\vcenter{\openup\jot
721 \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
723 $$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
724 c_i &\le \sum_e \left( 1 + \log \vert T_e\vert \right)&(Total cost of the binary searches.)\cr
725 &\le n_i + \sum_e \log\vert T_e\vert&(We sum over $n_i$ edges.)\cr
726 &\le n_i + n_i \cdot {\sum_e \log\vert T_e\vert \over n_i}&(Consider the average of logarithms.) \cr
727 &\le n_i + n_i \cdot \log{\sum_e \vert T_e\vert \over n_i}&(Logarithm is concave.) \cr
728 &\le n_i + n_i \cdot \log{q+n\over n_i}&(Bound the number of tops by queries.) \cr
729 &= n_i \cdot \left( 1 + \log\left({q+n\over n}\cdot{n\over n_i}\right) \right)\cr
730 &= n_i + n_i\log{q+n\over n} + n_i\log{n\over n_i}.\cr
732 Summing over all levels, we estimate the total number of comparisons as:
734 c = \sum_i c_i = \left( \sum_i n_i \right) + \left( \sum_i n_i \log{q+n\over n}\right) + \left( \sum_i n_i \log{n\over n_i}\right).
736 The first part is equal to~$n$, the second one to $n\log((q+n)/n)\le q+n$. For the third
737 one, we would like to plug in the bound $n_i \le n/2^i$, but we unfortunately have one~$n_i$
738 in the denominator. We save the situation by observing that the function $f(x)=x\log(n/x)$
739 is decreasing\foot{We can easily check the derivative: $f(x)=(x\ln n-x\ln x)/\ln 2$, so $f'(x)\cdot \ln2 =
740 \ln n - \ln x - 1$. We want $f'(x)<0$ and therefore $\ln x > \ln n - 1$, i.e., $x > n/e$.}
741 for $x > n/e$, so for $i\ge 2$ it holds that:
743 n_i\log{n\over n_i} \le {n\over 2^i}\cdot\log{n\over n/2^i} = {n\over 2^i} \cdot i.
745 We can therefore rewrite the third part as:
747 \sum_i n_i\log{n\over n_i} &\le n_0\log{n\over n_0} + n_1\log{n\over n_1} + n\cdot\sum_{i\ge 2}{i\over 2^i} \le\cr
748 &\le n\log1 + n_1\cdot {n\over n_1} + n\cdot\O(1) = \O(n).\cr
750 Putting all three parts together, we conclude that:
752 c \le n + (q+n) + \O(n) = \O(n+q). \qedmath
756 When we combine this lemma with the above reduction, we get the following theorem:
758 \thmn{Verification of the MST, Koml\'os \cite{komlos:verify}}\id{verify}%
759 For every weighted graph~$G$ and its spanning tree~$T$, it is sufficient to
760 perform $\O(m)$ comparisons of edge weights to determine whether~$T$ is minimum
761 and to find all $T$-light edges in~$G$.
764 We first transform the problem to finding all peaks of a~set
765 of query paths in~$T$ (these are exactly the paths covered by the edges
766 of $G\setminus T$). We use the reduction from Lemma \ref{verbranch} to get
767 an~equivalent problem with a~full branching tree and a~set of parent-descendant
768 paths. The reduction costs $\O(m+n)$ comparisons.
769 Then we run the \<FindPeaks> procedure (Algorithm \ref{findpeaks}) to find
770 the tops of all query paths. According to Lemma \ref{vercompares}, this spends another $\O(m+n)$
771 comparisons. Since we (as always) assume that~$G$ is connected, $\O(m+n)=\O(m)$.
775 The problem of computing path maxima or minima in a~weighted tree has several other interesting
776 applications. One of them is computing minimum cuts separating given pairs of vertices in a~given
777 weighted undirected graph~$G$. We construct a~Gomory-Hu tree~$T$ for the graph as described in \cite{gomoryhu}
778 (see also \cite{bhalgat:ght} for a~more efficient algorithm running in time
779 $\widetilde\O(mn)$ for unit-cost graphs). The crucial property of this tree is that for every two
780 vertices $u$, $v$ of the graph~$G$, the minimum-cost edge on $T[u,v]$ has the same cost
781 as the minimum cut separating $u$ and~$v$ in~$G$. Since the construction of~$T$ generally
782 takes $\Omega(n^2)$ time, we could of course invest this time in precomputing the minima for
783 all pairs of vertices. This would however require quadratic space, so we can better use
784 the method of this section which fits in $\O(n+q)$ space for $q$~queries.
787 A~dynamic version of the problem is also often considered. It calls for a~data structure
788 representing a~weighted forest with operations for modifying the structure of the forest
789 and querying minima or maxima on paths. Sleator and Tarjan have shown in \cite{sleator:trees}
790 how to do this in $\O(\log n)$ time amortized per operation, which leads to
791 an~implementation of the Dinic's maximum flow algorithm \cite{dinic:flow}
792 in time $\O(mn\log n)$.
794 %--------------------------------------------------------------------------------
796 \section{Verification in linear time}
798 We have proven that $\O(m)$ edge weight comparisons suffice to verify minimality
799 of a~given spanning tree. Now we will show an~algorithm for the RAM,
800 which finds the required comparisons in linear time. We will follow the idea
801 of King from \cite{king:verify}, but as we have the power of the RAM data structures
802 from Section~\ref{bitsect} at our command, the low-level details will be easier,
803 especially the construction of vertex and edge labels.
806 First of all, let us make sure that the reduction to fully branching trees
807 in Lemma \ref{verbranch} can be made run in linear time. As already noticed
808 in the proof, the Bor\o{u}vka's algorithm runs in linear time. Constructing
809 the Bor\o{u}vka tree in the process adds at most a~constant overhead to every
810 step of the algorithm.
812 Finding the common ancestors is not trivial, but Harel and Tarjan have shown
813 in \cite{harel:nca} that linear time is sufficient on the RAM. Several more
814 accessible algorithms have been developed since then (see the Alstrup's survey
815 paper \cite{alstrup:nca} and a~particularly elegant algorithm described by Bender
816 and Falach-Colton in \cite{bender:lca}). Any of them implies the following
819 \thmn{Lowest common ancestors}\id{lcathm}%
820 On the RAM, it is possible to preprocess a~tree~$T$ in time $\O(n)$ and then
821 answer lowest common ancestor queries presented online in constant time.
824 The reductions in Lemma \ref{verbranch} can be performed in time $\O(m)$.
827 Having the reduced problem at hand, it remains to implement the procedure \<FindPeaks>
828 of Algorithm \ref{findpeaks} efficiently. We need a~compact representation of
829 the arrays $T_e$ and~$P_e$, which will allow to reduce the overhead of the algorithm
830 to time linear will be linear in the number of comparisons performed. To achieve
831 this goal, we will encode the arrays in RAM vectors (see Section \ref{bitsect}
832 for the vector operations).
836 \em{Vertex identifiers:} Since all vertices processed by the procedure
837 lie on the path from the root to the current vertex~$u$, we modify the algorithm
838 to keep a~stack of these vertices in an~array. We will often refer to each vertex by its
839 index in this array, i.e., by its depth. We will call these identifiers \df{vertex
840 labels} and we note that each label requires only $\ell=\lceil \log\lceil\log n\rceil\rceil$
841 bits. As every tree edge is uniquely identified by its bottom vertex, we can
842 use the same encoding for \df{edge labels.}
844 \em{Slots:} As we will need several operations which are not computable
845 in constant time on the RAM, we precompute tables for these operations
846 like we did in the Q-heaps (cf.~Lemma \ref{qhprecomp}). A~table for word-sized
847 arguments would take too much time to precompute, so we will generally store
848 our data structures in \df{slots} of $s=\lceil 1/3\cdot\log n\rceil$ bits each.
849 We will show soon that it is possible to precompute a~table of any reasonable
850 function whose arguments fit in two slots.
852 \em{Top masks:} The array~$T_e$ will be represented by a~bit mask~$M_e$ called the \df{top mask.} For each
853 of the possible tops~$t$ (i.e., the ancestors of the current vertex), we store
854 a~single bit telling whether $t\in T_e$. Each top mask fits in $\lceil\log n\rceil$
855 bits and therefore in a~single machine word. If needed, it can be split to three slots.
856 Unions and intersections of sets of tops then translate to calling $\band$/$\bor$
859 \em{Small and big lists:} The heaviest edge found so far for each top is stored
860 by the algorithm in the array~$P_e$. Instead of keeping the real array,
861 we store the labels of these edges in a~list encoded in a~bit string.
862 Depending on the size of the list, we use one of two possible encodings:
863 \df{Small lists} are stored in a~vector which fits in a~single slot, with
864 the unused fields filled by a~special constant, so that we can easily infer the
867 If the data do not fit in a~small list, we use a~\df{big list} instead, which
868 is stored in $\O(\log\log n)$ words, each of them containing a~slot-sized
869 vector. Unlike the small lists, we use the big lists as arrays. If a~top~$t$ of
870 depth~$d$ is active, we keep the corresponding entry of~$P_e$ in the $d$-th
871 field of the big list. Otherwise, we keep that entry unused.
873 We want to perform all operations on small lists in constant time,
874 but we can afford spending time $\O(\log\log n)$ on every big list. This
875 is true because whenever we use a~big list, $\vert T_e\vert = \Omega(\log n/\log\log n)$,
876 hence we need $\log\vert T_e\vert = \Omega(\log\log n)$ comparisons anyway.
878 \em{Pointers:} When we need to construct a~small list containing a~sub-list
879 of a~big list, we do not have enough time to see the whole big list. To handle
880 this, we introduce \df{pointers} as another kind of edge identifiers.
881 A~pointer is an~index to the nearest big list on the path from the small
882 list containing the pointer to the root. As each big list has at most $\lceil\log n\rceil$
883 fields, the pointer fits in~$\ell$ bits, but we need one extra bit to distinguish
884 between normal labels and pointers.
886 \lemman{Precomputation of tables}
887 When~$f$ is a~function of two arguments computable in polynomial time, we can
888 precompute a~table of the values of~$f$ for all values of arguments that fit
889 in a~single slot. The precomputation takes $\O(n)$ time.
892 Similar to the proof of Lemma \ref{qhprecomp}. There are $\O(2^{2s}) = \O(n^{2/3})$
893 possible values of arguments, so the precomputation takes time $\O(n^{2/3}\cdot\poly(s))
894 = \O(n^{2/3}\cdot\poly(\log n)) = \O(n)$.
898 As we can afford spending spending $\O(n)$ time on preprocessing,
899 we can assume that we can compute the following functions in constant time:
902 \:$\<Weight>(x)$ --- the Hamming weight of a~slot-sized number~$x$
903 (we already considered this operation in Algorithm \ref{lsbmsb}, but we needed
904 quadratic word size for it). We can easily extend this to $\log n$-bit numbers
905 by splitting the number in three slots and adding their weights.
907 \:$\<FindKth>(x,k)$ --- the $k$-th set bit from the top of the slot-sized
908 number~$x$. Again, this can be extended to multi-slot numbers by calculating
909 the \<Weight> of each slot first and then finding the slot containing the
912 \:$\<Bits>(m)$ --- for a~slot-sized bit mask~$m$, it returns a~small list
913 of the positions of the bits set in~$\(m)$.
915 \:$\<Select>(x,m)$ --- constructs a~slot containing the substring of $\(x)$
916 selected by the bits set in~$\(m)$.
918 \:$\<SubList>(x,m)$ --- when~$x$ is a~small list and~$m$ a bit mask, it returns
919 a~small list containing the elements of~$x$ selected by the bits set in~$m$.
923 We will now show how to perform all parts of the procedure \<FindPeaks>
924 in the required time. We will denote the size of the tree by~$n$ and the
925 number of query paths by~$q$.
928 Depths of all vertices and all top masks can be computed in time $\O(n+q)$.
931 Run depth-first search on the tree, assign the depth of a~vertex when entering
932 it and construct its top mask when leaving it. The top mask can be obtained
933 by $\bor$-ing the masks of its sons, excluding the level of the sons and
934 including the tops of all query paths that have their bottoms at the current vertex
935 (the depths of the tops are already assigned).
939 The arrays $T_e$ and~$P_e$ can be indexed in constant time.
942 Indexing~$T_e$ is exactly the operation \<FindKth> applied on the corresponding
945 If $P_e$ is stored in a~big list, we calculate the index of the particular
946 slot and the position of the field inside the slot. This field can be then
947 extracted using bit masking and shifts.
949 If it is a~small list, we extract the field directly, but we have to
950 dereference it in case it is a pointer. We modify the recursion in \<FindPeaks>
951 to pass the depth of the lowest edge endowed with a~big list and when we
952 encounter a~pointer, we index this big list.
956 For an~arbitrary active top~$t$, the corresponding entry of~$P_e$ can be
957 extracted in constant time.
960 We look up the precomputed depth~$d$ of~$t$ first.
961 If $P_e$ is stored in a~big list, we extract the $d$-th entry of the list.
962 If the list is small, we find the position of the particular field
963 by counting bits of the top mask~$M_e$ at position~$d$ and higher
964 (this is \<Weight> of $M_e$ with the lower bits masked out).
968 The procedure \<FindPeaks> processes an~edge~$e$ in time $\O(\log \vert T_e\vert + q_e)$,
969 where $q_e$~is the number of query paths having~$e$ as its bottom edge.
972 The edge is examined in steps 1, 3, 4 and~5 of the algorithm. We will show how to
973 perform each of these steps in constant time if $P_e$ is a~small list or
974 $\O(\log\log n)$ if it is big.
976 \em{Step~1} looks up $q_e$~tops in~$P_e$ and we already know from Lemma \ref{verhe}
977 how to do that in constant time per top.
979 \em{Step~3} is trivial as we have already computed the top masks and we can
980 reconstruct the entries of~$T_e$ in constant time according to Lemma \ref{verth}.
982 \em{Step~5} involves binary search on~$P_e$ in $\O(\log\vert T_e\vert)$ comparisons,
983 each of them indexes~$P_e$, which is $\O(1)$ again by Lemma \ref{verth}. Rewriting the
984 lighter edges is $\O(1)$ for small lists by replication and bit masking, for a~big
985 list we do the same for each of its slots.
987 \em{Step~4} is the only non-trivial one. We already know which tops to select
988 (we have the top masks $M_e$ and~$M_p$ precomputed), but we have to carefully
990 We need to handle these four cases:
993 \:\em{Small from small:} We use $\<Select>(T_e,T_p)$ to find the fields of~$P_p$
994 that shall be deleted by a~subsequent call to \<SubList>. Pointers
995 can be retained as they still refer to the same ancestor list.
997 \:\em{Big from big:} We can copy the whole~$P_p$, since the layout of the
998 big lists is fixed and the items we do not want simply end up as unused
1001 \:\em{Small from big:} We use the operation \<Bits> to construct a~list
1002 of pointers (we use bit masking to add the ``this is a~pointer'' flags).
1004 \:\em{Big from small:} First we have to dereference the pointers in the
1005 small list~$S$. For each slot~$B_i$ of the ancestor big list, we construct
1006 a~subvector of~$S$ containing only the pointers referring to that slot,
1007 adjusted to be relative to the beginning of the slot (we use \<Compare>
1008 and \<Replicate> from Algorithm \ref{vecops} and bit masking). Then we
1009 use a~precomputed table to replace the pointers by the fields of~$B_i$
1010 they point to. We $\bor$ together the partial results and we again have
1013 Finally, we have to spread the fields of this small list to the whole big list.
1014 This is similar: for each slot of the big list, we find the part of the small
1015 list keeping the fields we want (we call \<Weight> on the sub-words of~$M_e$ before
1016 and after the intended interval of depths) and we use a~tabulated function
1017 to shift the fields to the right locations in the slot (controlled by the
1018 sub-word of~$M_e$ in the intended interval).
1022 \>We are now ready to combine these steps and get the following theorem:
1024 \thmn{Verification of MST on the RAM}\id{ramverify}%
1025 There is a~RAM algorithm, which for every weighted graph~$G$ and its spanning tree~$T$
1026 determines whether~$T$ is minimum and finds all $T$-light edges in~$G$ in time $\O(m)$.
1029 Implement the Koml\'os's algorithm from Theorem \ref{verify} with the data
1030 structures developed in this section.
1031 According to Lemma \ref{verfh}, it runs in time $\sum_e \O(\log\vert T_e\vert + q_e)
1032 = \O(\sum_e \log\vert T_e\vert) + \O(\sum_e q_e)$. The second sum is $\O(m)$
1033 as there are $\O(1)$ query paths per edge, the first sum is $\O(\#\hbox{comparisons})$,
1034 which is $\O(m)$ by Theorem \ref{verify}.
1038 Buchsbaum et al.~have recently shown in \cite{buchsbaum:verify} that linear-time
1039 verification can be achieved even on the pointer machine. They first solve the
1040 problem of finding the lowest common ancestors for a~set of pairs of vertices
1041 by batch processing. They combine an~algorithm of time complexity $\O(m\alpha(m,n))$
1042 using the Union-Find data structure with table lookup for small subtrees. Then they use a~similar
1043 technique for finding the peaks themselves. The tricky part is of course the table
1044 lookup, which they handle by radix-sorting pointer-based codes of the subtrees.
1047 The online version of this problem (build a~data structure for a~weighted tree
1048 in linear time and then answer queries for individual paths in constant time)
1049 is still open even for the RAM.
1051 %--------------------------------------------------------------------------------
1053 \section{A~randomized algorithm}\id{randmst}%
1055 When we analysed the contractive Bor\o{u}vka's algorithm in Section~\ref{contalg},
1056 we observed that while the number of vertices per iteration decreases exponentially,
1057 the number of edges can remain asymptotically the same. Karger, Klein and Tarjan
1058 \cite{karger:randomized} have overcome this problem by combining the Bor\o{u}vka's
1059 algorithm with filtering based on random sampling. This leads to a~randomized
1060 algorithm which runs in expected linear time.
1062 As we will need the algorithm for verification of minimality from the previous
1063 section, we will again assume that we are working on the RAM.
1065 The principle of the filtering is simple: Let us consider any spanning tree~$T$
1066 of the input graph~$G$. Each edge of~$G$ that is $T$-heavy is the heaviest edge
1067 of some cycle, so by the Red lemma (\ref{redlemma}) it cannot participate in
1068 the MST of~$G$. We can therefore discard all $T$-heavy edges and continue with
1069 finding the MST on the reduced graph. Not all choices of~$T$ are equally good,
1070 but the following lemma shows that when we take~$T$ as a~MST of a~randomly selected
1071 subgraph, only a~small expected number of edges remain.
1074 The random sampling will sometimes select a~disconnected subgraph,
1075 so we will not assume connectedness in this section. As we already noted
1076 (Remark \ref{disconn}), with a~little bit of care our algorithms and theorems
1077 keep working. We also extend the notion of light and heavy edges with respect
1078 to a~tree to forests: When an~edge~$e$ connects two vertices lying in the same
1079 tree~$T$ of a~forest~$F$, it is $F$-heavy iff it is $T$-heavy (similarly
1080 for $F$-light). Edges connecting two different trees are always considered
1081 $F$-light. Again, a~spanning forest~$F$ is minimum iff there are no $F$-light
1084 \lemman{Random sampling, Karger \cite{karger:sampling}}
1085 Let $H$~be a~subgraph of~$G$ obtained by including each edge independently
1086 with probability~$p$ and $F$~the minimum spanning forest of~$H$. Then the
1087 expected number of $F$-nonheavy edges in~$G$ is at most $n/p$.
1090 Let us observe that we can obtain the forest~$F$ by combining the Kruskal's algorithm
1091 (\ref{kruskal}) with the random process producing~$H$ from~$G$. We sort all edges of~$G$
1092 by their weights and start with an~empty forest~$F$. For each edge, we first
1093 flip a~biased coin (it gives heads with probability~$p$) and if it comes up
1094 tails, we discard the edge. Otherwise we perform a~single step of the Kruskal's
1095 algoritm: We check if~$F+e$ contains a~cycle. If it does, we discard~$e$, otherwise
1096 we add~$e$ to~$F$. At the end, we have produced the subgraph~$H$ and its MSF~$F$.
1098 We can modify the algorithm by swapping the check for cycles with flipping of
1101 \:If $F+e$ contains a~cycle, we immediately discard~$e$ (we can flip
1102 the coin, but we need not to, because the edge will be discarded regardless of
1103 the outcome). We note that~$e$ is $F$-heavy with respect to both the
1104 current~$F$ and the final MSF.
1105 \:If $F+e$ is acyclic, we flip the coin:
1106 \::If it comes up heads, we add~$e$ to~$F$. In this case, $e$~is neither $F$-light
1108 \::If it comes up tails, we discard~$e$. Such edges are $F$-light.
1111 The number of $F$-nonheavy edges is therefore equal to the number of the coin
1112 flips in step~2 of this algorithm. We also know that the algorithm stops before
1113 it adds $n$~edges to~$F$. Therefore it flips at most as many coins as a~simple
1114 random process which repeatedly flips until it gets~$n$ heads. As waiting for
1115 every occurence of heads takes expected time~$1/p$, waiting for~$n$ heads
1116 must take $n/p$. This is the bound we wanted to achieve.
1120 We will formulate the algorithm as a~doubly-recursive procedure. It alternatively
1121 peforms steps of the Bor\o{u}vka's algorithm and filtering based on the above lemma.
1122 The first recursive call computes the MSF of the sampled subgraph, the second one
1123 finds the MSF of the graph without the heavy edges.
1125 As in all contractive algorithms, we use edge labels to keep track of the
1126 original locations of the edges in the input graph. For the sake of simplicity,
1127 we do not mention it in the algorithm.
1129 \algn{MSF by random sampling --- the KKT algorithm}
1131 \algin A~graph $G$ with an~edge comparison oracle.
1132 \:Remove isolated vertices from~$G$. If no vertices remain, stop and return an~empty forest.
1133 \:Perform two Bor\o{u}vka steps (iterations of Algorithm \ref{contbor}) on~$G$ and
1134 remember the set~$B$ of edges contracted.
1135 \:Select subgraph~$H\subseteq G$ by including each edge independently with
1137 \:$F\=\msf(H)$ calculated recursively.
1138 \:Construct $G'\subseteq G$ by removing all $F$-heavy edges.
1139 \:$R\=\msf(G')$ calculated recursively.
1141 \algout The minimum spanning forest of~$G$.
1145 Let us analyse the time complexity this algorithm by studying properties of its \df{recursion tree.}
1146 The tree describes the subproblems processed by the recursive calls. For any vertex~$t$
1147 of the tree, we denote the number of vertices and edges of the corresponding subproblem~$G_t$
1148 by~$n_t$ and~$m_t$ respectively. If $m_t>0$, the recursion continues: the left son of~$t$
1149 corresponds to the call on the sampled subgraph~$H$, the right son to the reduced
1150 graph~$G'$. The root of the recursion tree is obviously the original graph~$G$, the
1151 leaves are trivial graphs with no edges.
1154 The Bor\o{u}vka steps together with the removal of isolated vertices guarantee that the number
1155 of vertices drops at least by a~factor of four in every recursive call. The size of a~subproblem~$G_t$
1156 at level~$\ell$ is therefore at most $n/4^\ell$ and the depth of the tree is at most $\lceil\log_4 n\rceil$.
1157 As there are no more than~$2^\ell$ subproblems at level~$\ell$, the sum of all~$n_t$'s
1158 on that level is at most $n/2^\ell$, which is at most~$2n$ summed over the whole tree.
1161 For every subproblem~$G_t$, the KKT algorithm spends time $\O(m_t+n_t)$ plus the time
1162 spent on the recursive calls.
1165 We know from Lemma \ref{contiter} that each Bor\o{u}vka step takes time $\O(m_t+n_t)$.\foot{We
1166 add $n_t$ as the graph could be disconnected.}
1167 The selection of the edges of~$H$ is straightforward.
1168 Finding the $F$-heavy edges is not, but we have already shown in Theorem \ref{ramverify}
1169 that linear time is sufficient on the RAM.
1172 \thmn{Worst-case complexity of the KKT algorithm}
1173 The KKT algorithm runs in time $\O(\min(n^2,m\log n))$ in the worst case on the RAM.
1175 \thmn{Average-case complexity of the KKT algorithm}
1178 We could also use a~slightly different formulation of the sampling lemma
1179 suggested by Chan \cite{chan:backward}. It changes the selection of the subgraph~$H$
1180 to choosing an~$mp$-edge subset of~$E(G)$ uniformly at random. The proof is then
1181 a~straightforward application of the backward analysis method. We however prefered
1182 the Karger's original version, because generating a~random subset of a~given size
1183 cannot be generally performed in bounded worst-case time.
1185 \FIXME{Pointer machine.}
1187 %--------------------------------------------------------------------------------
1189 \section{Special cases and related problems}
1191 Finally, we will focus our attention on various special cases of the minimum
1192 spanning tree problem which frequently arise in practice.
1194 \examplen{Graphs with sorted edges}
1195 When the edges are already sorted by their weights, we can use the Kruskal's
1196 algorithm to find the MST in time $\O(m\timesalpha(n))$ (Theorem \ref{kruskal}).
1197 We however can do better: As the minimality of a~spanning tree depends only on the
1198 order of weights and not on the actual values (Theorem \ref{mstthm}), we can
1199 renumber the weights to $1, \ldots, m$ and find the MST using the Fredman-Willard
1200 algorithm for integer weights. According to Theorem \ref{intmst} it runs in
1201 time $\O(m)$ on the Word-RAM.
1203 \examplen{Graphs with a~small number of distinct weights}
1204 When the weights of edges are drawn from a~set of a~fixed size~$U$, we can
1205 sort them in linear time and so reduce the problem to the previous case.
1206 A~more practical way is to use the Jarn\'\i{}k's algorithm (\ref{jarnimpl}),
1207 but replace the heap by an~array of $U$~buckets. As the number of buckets
1208 is constant, we can find the minimum in constant time and hence the whole
1209 algorithm runs in time $\O(m)$, even on the Pointer Machine. For large
1210 values of~$U,$ we can build a~binary search tree or the van Emde-Boas
1211 tree (see Section \ref{ramdssect} and \cite{boas:vebt}) on the top of the buckets to bring the complexity
1212 of finding the minimum down to $\O(\log U)$ or $\O(\log\log U)$ respectively.
1214 \examplen{Graphs with floating-point weights}
1215 A~common case of non-integer weights are rational numbers in floating-point (FP)
1216 representation. Even in this case we will be able to find the MST in linear time.
1217 The most common representation of binary FP numbers specified by the IEEE
1218 standard 754-1985 \cite{ieee:binfp} has a~useful property: When the
1219 bit strings encoding non-negative FP numbers are read as ordinary integers,
1220 the order of these integers is the same as of the original FP numbers. We can
1221 therefore once again replace the edge weights by integers and use the linear-time
1222 integer algorithm. While the other FP representations (see \cite{dgoldberg:fp} for
1223 an~overview) need not have this property, the corresponding integers can be adjusted
1224 in $\O(1)$ time to the format we need. (More advanced tricks of this type have been
1225 employed by Thorup in \cite{thorup:floatint} to extend his linear-time algorithm
1226 for single-source shortest paths to FP edge lengths.)
1228 \examplen{Graphs with bounded degrees}
1229 For graphs with vertex degrees bounded by a~constant~$\Delta$, the problem is either
1230 trivial (if $\Delta<3$) or as hard as for arbitrary graphs. There is a~simple linear-time
1231 transform of arbitrary graphs to graphs with maximum degree~3 which preserves the MST:
1233 \lemman{Degree reduction}\id{degred}%
1234 For every graph~$G$ there exists a~graph~$G'$ with maximum degree at most~3 and
1235 a~function $\pi: E(G)\rightarrow E(G')$ such that $\mst(G) = \pi^{-1}(\mst(G'))$.
1236 The graph $G'$ and the embedding~$\pi$ can be constructed in time $\O(m)$.
1238 \figure{french.eps}{\epsfxsize}{Degree reduction in Lemma~\ref{degred}}
1241 We show how to eliminate a~single vertex~$v$ of degree $d>3$ and then apply
1244 Assume that $v$~has neighbors $w_1,\ldots,w_d$. We replace~$v$ and the edges~$vw_i$
1245 by $d$~new vertices $v_1,\ldots,v_d$, joined by a~path $v_1v_2\ldots v_d$, and
1246 edges~$v_iw_i$. Each edge of the path will receive a~weight smaller than all
1247 original weights, the other edges will inherit the weights of the edges $vw_i$
1248 they replace. The edges of the path will therefore lie in the MST (this is
1249 obvious from the Kruskal's algorithm) and as~$G$ can be obtained from the
1250 new~$G'$ by contracting the path, the rest follows from the Contraction lemma
1253 This step can be carried out in time $\O(d)$. As it replaces a high-degree
1254 vertex by vertices of degree~3, the whole procedure stops in at most~$n$ such
1255 steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$ including the
1256 time needed to find the high-degree vertices at the beginning.
1259 \examplen{Euclidean MST}
1260 The MST also has its counterparts in the realm of geometric algorithms. Suppose
1261 that we have $n$~points $x_1,\ldots,x_n$ in the plane and we want to find the
1262 shortest system of segments connecting these points. If we want the segments to
1263 touch only in the given points, this is equivalent to finding the MST of the
1264 complete graph on the vertices $V=\{x_1,\ldots,x_n\}$ with edge weights
1265 defined as the Euclidean distances of the points. Since the graph is dense, many of the MST
1266 algorithms discussed run in linear time with the size of the graph, hence
1269 There is a~more efficient method based on the observation that the MST
1270 is always a~subgraph of the Delaunay's tesselation for the given points
1271 (this was first noted by Shamos and Hoey in~\cite{shamos:closest}). The
1272 tesselation is a~planar graph, which guarantees that it has $\O(n)$ edges,
1273 and it is a~dual graph of the Voronoi diagram of the given points, which can
1274 be constructed in time $\O(n\log n)$ using for example the Fortune's
1275 algorithm \cite{fortune:voronoi}. We can therefore reduce the problem
1276 to finding the MST of the tesselation for which $\O(n\log n)$ time
1277 is more than sufficient.
1279 This approach fails for non-Euclidean metrics, but in some cases
1280 (in particular for the rectilinear metric) the $\O(n\log n)$ time bound
1281 is also achievable by the algorithm of Zhou et al.~\cite{zhou:nodel}
1282 based on the sweep-line technique and the Red rule. For other
1283 variations on the geometric MST, see Eppstein's survey paper
1284 \cite{eppstein:spanning}.
1286 \examplen{Steiner trees}
1287 The constraint that the segments in the previous example are allowed to touch
1288 each other only in the given points looks artificial and it is indeed uncommon in
1289 practical applications (including the problem of designing electrical transmission
1290 lines originally studied by Bor\o{u}vka). If we lift this restriction, we get
1291 the problem known by the name Steiner tree.\foot{It is named after the Swiss mathematician
1292 Jacob Steiner who studied a~special case of this problem in the 19th century.}
1293 We can also define it in terms of graphs:
1295 \defn A~\df{Steiner tree} of a~weighted graph~$(G,w)$ with a~set~$M\subseteq V$
1296 of \df{mandatory notes} is a~tree~$T\subseteq G$ that contains all the mandatory
1297 vertices and its weight is minimum possible.
1299 For $M=V$ the Steiner tree is identical to the MST, but if we allow an~arbitrary
1300 choice of the mandatory vertices, it is NP-hard. This has been proven by Garey and Johnson
1301 \cite{garey:steiner,garey:rectisteiner} for not only the graph version with
1302 weights $\{1,2\}$, but also for the planar version with Euclidean or rectilinear
1303 metric. There is a~polynomial approximation algorithm with ratio $5/3$ for
1304 graphs due to Pr\"omel and Steger \cite{proemel:steiner} and a~polynomial-time
1305 approximation scheme for the Euclidean Steiner tree in an~arbitrary dimension
1306 by Arora \cite{arora:tspapx}.
1308 \examplen{Approximating the weight of the MST}
1309 Sometimes we are not interested in the actual edges forming the MST and only
1310 the weight matters. If we are willing to put up with a~randomized approximation,
1311 we can even achieve sub-linear complexity. Chazelle et al.~\cite{chazelle:mstapprox}
1312 have shown an~algorithm which, given $0 < \varepsilon < 1/2$, approximates
1313 the weight of the MST of a~graph with average degree~$d$ and edge weights from the set
1314 $\{1,\ldots,w\}$ in time $\O(dw\varepsilon^{-2}\cdot\log(dw/\varepsilon))$,
1315 producing a~weight which has relative error at most~$\varepsilon$ with probability
1316 at least $3/4$. They have also proven an~almost matching lower bound $\Omega(dw\varepsilon^{-2})$.
1318 For the $d$-dimensional Euclidean case, there is a~randomized approximation
1319 algorithm by Czumaj et al.~\cite{czumaj:euclidean} which with high probability
1320 produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\sqrt{n}\cdot \poly(1/\varepsilon))$\foot{%
1321 $\widetilde\O(f) = \O(f\cdot\log^{\O(1)} f)$ and $\poly(n)=n^{\O(1)}$.}
1322 queries to a~data structure containing the points. The data structure is expected
1323 to answer orthogonal range queries and cone approximate nearest neighbor queries.
1324 There is also a~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation
1325 algorithm for the MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}.
1326 (This is still sub-linear since the corresponding graph has roughly $n^2$ edges.)