]> mj.ucw.cz Git - saga.git/blob - opt.tex
Parts of preface.
[saga.git] / opt.tex
1 \ifx\endpart\undefined
2 \input macros.tex
3 \fi
4
5 \chapter{Approaching Optimality}\id{optchap}%
6
7 \section{Soft heaps}\id{shsect}%
8
9 A~vast majority of MST algorithms that we have encountered so far is based on
10 the Tarjan's Blue rule (Lemma \ref{bluelemma}). The rule serves to identify
11 edges that belong to the MST, while all other edges are left in the process. This
12 unfortunately means that the later stages of computation spend most of
13 their time on these useless edges. A~notable exception is the randomized
14 algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses
15 Red rule (Lemma \ref{redlemma}) to filter out edges that are guaranteed to stay
16 outside the MST, so that the graphs with which the algorithm works get smaller
17 with time.
18
19 Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}
20 have presented new deterministic algorithms for the MST which are also based
21 on the combination of both rules. They have reached worst-case time complexity
22 $\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to their results
23 and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal}
24 which is provably optimal.
25
26 At the very heart of all these algorithms lies the \df{soft heap} discovered by
27 Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
28 similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
29 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
30 the expense of \df{corrupting} a~fraction of the inserted elements by raising
31 their values (the values are however never lowered). This allows for
32 an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$.
33 The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
34 moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be
35 corrupted.
36
37 \defnn{Soft heap operations}%
38 The soft heap contains a~set of distinct items from a~totally ordered universe and it
39 supports the following operations:
40 \itemize\ibull
41 \:$\<Create>(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$.
42 \:$\<Insert>(H,x)$ --- Insert a~new item~$x$ to the heap~$H$.
43 \:$\<Meld>(P,Q)$ --- Merge two heaps into one, more precisely move all items of a~heap~$Q$
44   to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$).
45 \:$\<DeleteMin>(H)$ --- Delete the minimum item of the heap~$H$ and return its value
46   (optionally signalling that the value has been corrupted).
47 \:$\<Explode>(H)$ --- Destroy the heap and return a~list of all items contained in it
48   (again optionally marking those corrupted).
49 \endlist
50
51 \examplen{Linear-time selection}
52 We can use soft heaps to select the median (or generally the $k$-th smallest element)
53 of a~sequence. We insert all $n$~elements to a~soft heap with error rate $\varepsilon=1/3$.
54 Then we delete the minimum about $n/3$ times and we remember the current (possibly corrupted)
55 value~$x$ of the last element deleted. This~$x$ is greater or equal than the current
56 values of the previously deleted elements and thus also than their correct values.
57 On the other hand, the current values of the $2n/3$ elements remaining in the heap
58 are greater than~$x$ and at most $n/3$ of them are corrupted. Therefore at least $n/3$
59 elements are greater than~$x$ and at least $n/3$ ones are smaller. Depending on the value
60 of~$k$, we can always throw away one of these parts and recurse on the rest (similarly to
61 the Hoare's Quickselect algorithm \cite{hoare:qselect}). The total time complexity will
62 be $\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$. We have obtained a~nice alternative to the standard
63 linear-time selection algorithm by Blum \cite{blum:selection}. The same trick can be used
64 to select a~good pivot in Quicksort \cite{hoare:qsort}, leading to time complexity $\O(n\log n)$
65 in the worst case.
66
67 \defnn{Soft queues}
68 The soft heap is built from \df{soft queues} (we will usually omit the adjective soft
69 in the rest of this section). Each queue has a~shape of a~binary tree.\foot{%
70 Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are
71 somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary
72 trees with a~special distribution of values. In fact, the original C~code in the Chazelle's
73 paper \cite{chazelle:softheap} uses this representation internally.}
74 Each vertex~$v$ of the tree remembers a~doubly-linked list of items. The
75 item list in every left son will be used only temporarily and it will be kept
76 empty between operations. Only right sons and the root have their lists
77 permanently occupied. The left sons will be called \df{white}, the right ones
78 \df{black.} (See the picture.)
79
80 The first value in every list is called the \df{controlling key} of the vertex,
81 denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
82 value or we set $\<ckey>(v)=+\infty$. The \<ckey> obey the standard \df{heap order}
83 --- a~\<ckey> of a~parent is always smaller than the \<ckey>'s of its sons.
84
85 Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
86 The ranks of leaves are always zero, the rank of every internal vertex can be
87 arbitrary, but it must be strictly greater than the ranks of its sons. We
88 define the rank of the whole queue to be equal to the rank of its root vertex and
89 similarly for its \<ckey>.
90
91 A~queue is called \df{complete} if every two vertices joined by an~edge have rank
92 difference exactly one. In other words, it is a~complete binary tree and the
93 ranks correspond to vertex heights.
94
95 \figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\
96 (black vertices contain items, numbers indicate ranks)}}
97
98 \obs
99 The complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are
100 black (by induction). Any other queue can be trivially embedded to the complete queue of the same
101 rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex
102 ranks, colors and the ancestor relation.
103
104 The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
105 two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
106 of the original roots and also its \<ckey>. To preserve the heap order, we will choose
107 the one whose \<ckey> is smaller.
108
109 Sometimes, we will also need to split a~queue to smaller queues. We will call this operation
110 \df{dismantling} the queue and it will happen only in cases when the item list in the root
111 is empty. It suffices to remove the leftmost (all white) path going from the root. From
112 a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing
113 if the original queue was not complete.
114
115 \figure{softheap2.eps}{\epsfxsize}{Joining and dismantling of soft queues}
116
117 We will now define the real soft heap and the operations on it.
118
119 \defn A~\df{soft heap} consists of:
120 \itemize\ibull
121 \:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks),
122   we will call the first queue the \df{head} of the list, the last queue will be its \df{tail};
123 \:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \<ckey>
124 of those following it in the list;
125 \:a~global parameter~$r$: an~even integer to be set depending on~$\varepsilon$.
126 \endlist
127
128 \>We will define the \df{rank} of a~heap as the highest of the ranks of its queues
129 (that is, the rank of the heap's tail).
130
131 The heap always keeps the \df{Rank invariant:} When a~root of any tree has rank~$k$,
132 its leftmost path contains at least~$k/2$ vertices.
133
134 \paran{Operations on soft heaps}
135
136 \em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble
137 the heap of the smaller rank and we insert its queues to the other heap.
138 If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
139 a~single queue of rank~$k+1$ as already described and we propagate the new queue as
140 a~\df{carry} to the next iteration, similarly to addition of binary numbers.
141 Finally we have to update the suffix minima by walking the new list backwards
142 from the last inserted item.
143
144 \em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
145 a~single-element heap and melding it to the destination heap.
146
147 \algn{Creating a~new soft heap}
148 \algo
149 \algin The~parameter~$\varepsilon$ (the accuracy of the heap).
150 \:Allocate memory for a~new heap structure~$H$.
151 \:Initialize the list of queues in~$H$ to an~empty list.
152 \:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later).
153 \algout A~newly minted soft heap~$H$.
154 \endalgo
155
156 \algn{Melding of two soft heaps}
157 \algo
158 \algin Two soft heaps~$P$ and~$Q$.
159 \:If $\<rank>(P) < \<rank>(Q)$, exchange the item lists of~$P$ and~$Q$.
160 \:$p\=\<head>(P)$.
161 \brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that
162 there is an~empty queue of infinite rank there.}
163 \:While $Q$ still has some queues:
164 \::$q\=\<head>(Q)$.
165 \::If $\<rank>(p) < \<rank>(q)$, then $p\=$ the successor of~$p$,
166 \::else if $\<rank>(p) > \<rank>(q)$, remove~$q$ from~$Q$ and insert it to~$P$ before~$p$,
167 \::otherwise (the ranks are equal, we need to propagate the carry):
168 \:::$\<carry>\=p$.
169 \:::Remove~$p$ from~$P$ and set $p\=$ the original successor of~$p$.
170 \:::While $\<rank>(q)=\<rank>(\<carry>)$:
171 \::::Remove~$q$ from~$Q$.
172 \::::$\<carry>\=\<join>(q, \<carry>)$.
173 \::::$q\=\<head>(Q)$.
174 \:::Insert~\<carry> before~$q$.
175 \:Update the suffix minima: Walk with~$p$ backwards to the head of~$P$:
176 \::$p'\=\<suffix\_min>$ of the successor of~$p$.
177 \::If $\<ckey>(p) < \<ckey>(p')$, set $\<suffix\_min>(p)\=p$.
178 \::Otherwise set $\<suffix\_min>(p)\=p'$.
179 \:Destroy the heap~$Q$.
180 \algout The merged heap~$P$.
181 \endalgo
182
183 \algn{Insertion of an~element to a~soft heap}
184 \algo
185 \algin A~heap~$H$ and a~new element~$x$.
186 \:Create a~new heap~$H'$ of the same parameters as~$H$. Let~$H'$ contain a~sole queue of rank~0,
187   whose only vertex has the element~$x$ in its item list.
188 \:$\<Meld>(H,H')$.
189 \algout An~updated heap~$H$.
190 \endalgo
191
192 \para
193 So far, the mechanics of the soft heaps were almost identical to the binomial heaps
194 and the reader could rightfully yawn. The things are going to get interesting
195 now as we approach the parts where corruption of items takes place.
196
197 If all item lists contain at most one item equal to the \<ckey> of the particular
198 vertex, no information is lost and the heap order guarantees that the minimum item
199 of every queue stays in its root. We can however allow longer lists and let the items
200 stored in a~single list travel together between the vertices of the tree, still
201 represented by a~common \<ckey>. This data-structural analogue of car pooling will
202 allow the items to travel at a~faster rate, but as only a~single item can be equal
203 to the \<ckey>, all other items will be inevitably corrupted.
204
205 We of course have to be careful about the size of the lists, because we must avoid corrupting
206 too many items. We will control the growth according to the vertex ranks. Vertices
207 with rank at most~$r$ will always contain just a~single item. Above this level,
208 the higher is the rank, the longer list will be allowed.
209
210 \para
211 \em{Deletion of minimum} will be based on this principle. The minimum is easy to locate
212 --- we follow the \<suffix\_min> of the head of the heap to the queue with the minimum
213 \<ckey>. There we look inside the item list of the root of the queue. We remove the \em{last}
214 item from the list (we do not want the \<ckey> to change) and we return it as the minimum.
215 (It is not necessarily the real minimum of all items, but always the minimum of their
216 possibly corrupted values.)
217
218 If the list becomes empty, we \em{refill} it with items from the lower levels of the
219 same queue. This process can be best described recursively: We ask the left son to refill itself
220 (remember that the left son is always white, so there are currently no items there). If the new
221 \<ckey> of the left son is smaller than of the right son, we immediately move the left
222 son's list to its parent. Otherwise, we exchange the sons and move the list from the
223 new left son to the parent. This way we obey the heap order and at the same time we keep
224 the white left son free of items.
225
226 Occasionally, we repeat this process once again and we concatenate the resulting lists
227 (we append the latter list to the former, using the smaller of the two \<ckey>'s). This
228 makes the lists grow longer and we want to do that roughly on every other level of the
229 tree. The exact condition will be that either the rank of the current vertex is odd,
230 or the difference in ranks between this vertex and its right son is at least two.
231
232 If refilling of the left son fails because there are no more items in that subtree
233 (we report this by setting its \<ckey> to $+\infty$), the current vertex is no longer
234 needed --- the items would just pass through it unmodified. We therefore want to
235 remove it. Instead of deleting it directly, we rather make it point to its former
236 grandsons and we remove the (now orphaned) original son. This helps us to ensure
237 that both sons always keep the same rank, which will be useful for the analysis.
238
239 When all refilling is done, we update the suffix minima by walking from the current
240 queue to the head of the heap exactly as we did in the \<Meld> procedure.
241
242 Our only remaining worry is that the Rank invariant can be broken after the
243 refilling. When the leftmost path of the tree becomes too short, we just
244 \em{dismantle} the tree as already described and we meld the new trees back to
245 the heap. This is easier to handle when the item list at the root vertex is
246 empty. We will therefore move this check before the refilling of the root list.
247 It will turn out that we have enough time to always walk the leftmost path
248 completely, so no explicit counters are needed.
249
250 Let us translate these ideas to real (pseudo)code:
251
252 \algn{Deleting the minimum item from a~soft heap}
253 \algo
254 \algin A~soft heap~$H$.
255 \:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
256 \:Remove the final element~$x$ of the item list in the root of~$q$.
257 \:If the item list is empty:
258 \::Count the vertices on the leftmost path of~$q$.
259 \::If there are less than $\<rank>(q)$ of them:
260 \:::Remove~$q$ from the list of queues.
261 \:::Recalculate the suffix minima as in the \<Meld> procedure.
262 \:::Dismantle~$q$ and create a~heap~$H'$ holding the resulting trees.
263 \:::Meld them back: $\<Meld>(H,H')$.
264 \::Otherwise:
265 \:::Call \<Refill> on the root of~$q$.
266 \:::If $\<ckey>(q)=+\infty$ (no items left), remove the tree~$q$ from~$H$.
267 \:::Recalculate the suffix minima.
268 \algout The deleted minimum item~$x$ (possibly corrupted).
269 \endalgo
270
271 \algn{Refilling the item list of a~vertex}
272 \algo
273 \algin A~soft queue and its vertex~$v$ with an~empty item list.
274 \:Handle trivial cases: If~$v$ has no children or both have $\<ckey>=+\infty$,
275   set $\<ckey>(v)$ to~$+\infty$ and return.
276 \:Let \<left> and~\<right> denote the respective sons of~$v$.
277 \:Recurse: call $\<Refill>(\<left>)$.
278 \:If $\<ckey>(\<left>) > \<ckey>(\<right>)$, swap the sons.
279 \:Move the item list from \<left> to~$v$ (implying $\<ckey>(v)=\<ckey>(\<left>)$).
280 \:If $\<rank>(v) > r$ and either $\<rank>(v)$ is odd or $\<rank>(v) > \<rank>(\<right>)+1$, recurse once more:
281 \::Repeat steps 3--4.
282 \::Append the item list from \<left> to the item list at~$v$.
283 \:Clean up. If $\<ckey>(\<right>) = +\infty$:
284 \::If $\<ckey>(\<left>) = +\infty$, unlink and discard both sons.
285 \::Otherwise relink the sons of \<left> to~$v$ and discard \<left>.
286 \algout A~modified soft queue.
287 \endalgo
288
289 \para
290 \<Explode> is trivial once we know how to recognize the corrupted items. It simply examines
291 all queues in the heap, walks the trees and the item lists of all vertices. It records
292 all items seen, the corrupted ones are those that different from their \<ckey>.
293
294 \paran{Analysis of accuracy}%
295 The description of the operations is now complete, so let us analyse their behavior
296 and verify that we have delivered what we promised --- first the accuracy of
297 the structure, then the time complexity of operations. In the whole analysis,
298 we will denote the total number of elements inserted during the history of the
299 structure by~$n$. We will also frequently take advantage of knowing that the
300 threshold~$r$ is even.
301
302 We start by bounding the sizes of the item lists.
303
304 \lemma
305 For every vertex~$v$ of a~soft queue, the size $\ell(v)$ of its item list
306 satisfies:
307 $$\ell(v) \le \max(1, 2^{\lceil \<rank>(v)/2 \rceil - r/2}).$$
308
309 \proof
310 Initially, all item lists contain at most one item, so the inequality trivially
311 holds. Let us continue by induction. Melds can affect it only in the favorable
312 direction (they occasionally move an~item list to a~vertex of a~higher rank)
313 and so do deletes (they only remove items from lists). The only potentially
314 dangerous place is the \<Refill> procedure.
315
316 Refilling sometimes just moves items upwards, which is safe, and sometimes it
317 joins two lists into one, which generally is not. When $\<rank>(v) \le r$,
318 no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either
319 $\<rank>(v)$ is odd or $\<rank>(w) < \<rank>(v)-1$ for any son~$w$ of~$v$ (remember
320 that both sons have the same rank). In both cases, $\lceil\<rank>(w)/2\rceil \le
321 \lceil\<rank>(v)/2\rceil - 1$. By the induction hypothesis, the size of each
322 of the two joined lists is at most $2^{\max(1,\lceil\<rank>(v)/2\rceil - 1 - r/2)}$,
323 so the new list has at most $2^{\lceil\<rank>(v)/2\rceil - r/2}$ items. (The maximum
324 has disappeared since $\<rank>(v)>r$ and therefore the desired bound is at least~2.)
325 \qed
326
327 We will now sum the sizes of the lists over all vertices containing corrupted items.
328
329 \lemma\id{shcorrlemma}%
330 At any given time, the heap contains at most~$n/2^{r-2}$ corrupted items.
331
332 \proof
333 We first prove an~auxiliary claim: The master trees of all queues contain at most~$n$
334 black vertices. This follows by induction: If no deletions have taken place,
335 there are exactly~$n$ black vertices, because insertion adds one black vertex and
336 melding preserves their number. A~deletion affects the master trees only when
337 dismantling takes place and then it only removes a~black vertex.
338
339 An~obvious upper bound on the number of corrupted items is the total size of item
340 lists in all vertices of rank greater than~$r$. We already know from the previous
341 lemma that the list sizes are limited by a~function of the ranks. A~complete tree
342 is obviously the worst case, so we will prove that this lemma holds for the master
343 tree of every queue in the heap. The actual trees can be much sparser, but the
344 above claim guarantees that the total size of the master trees is bounded by the
345 number of insertions properly.
346
347 So let us consider a~complete tree of~rank~$k$. It has exactly $2^{k-i}$ vertices
348 of rank~$i$ and each such vertex contains a~list of at most~$2^{\lceil i/2\rceil - r/2}$
349 items by the previous lemma. Summing over all ranks greater than~$r$, we get that
350 the total number of corrupted items in this tree is at most:
351 $$
352 \sum_{i=r+1}^k 2^{k-i}\cdot 2^{\lceil i/2\rceil - r/2}
353 = 2^{k-r/2} \cdot \sum_{i=r+1}^k 2^{\lceil i/2\rceil - i}
354 \le 2^{k-r/2+1/2} \cdot \sum_{i=r+1}^k 2^{-i/2}
355 \le 2^{k-r} \cdot \sum_{i=0}^\infty 2^{-i/2}.
356 $$
357 The sum of a~geometric series with quotient $2^{-1/2}$ is less than four, so the
358 last expression is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ black vertices,
359 this makes less than $n_k/2^{r-2}$ corrupted items as we asserted.
360 \qed
361
362 \paran{Analysis of time complexity}%
363 Now we will examine the amortized time complexity of the individual operations.
364 We will show that if we charge $\O(r)$ time against every element inserted, it is enough
365 to cover the cost of all other operations.
366
367 All heap operations use only pointer operations, so it will be easy to derive the time
368 bound in the Pointer Machine model. The notable exception is however that the procedures
369 often refer to the ranks, which are integers on the order of $\log n$, so they cannot
370 fit in a~single memory cell. For the time being, we will assume that the ranks can
371 be manipulated in constant time, postponing the proof for later.
372
373 We take a~look at the melds first.
374
375 \lemma\id{shmeld}%
376 The amortized cost of a~meld is $\O(1)$, except for melds induced by dismantling
377 which take $\O(\<rank>(q))$, where $q$~is the queue to be dismantled.
378
379 \proof
380 The real cost of a~meld of heaps $P$ and~$Q$ is linear in the smaller of
381 their ranks, plus the time spent on carry propagation. The latter is easy to
382 dispose of: Every time there is a~carry, the total number of trees in all
383 heaps decreases by one. So it suffices to charge $\O(1)$ against creation of
384 a~tree. An~insert creates one tree, dismantling creates at most $\<rank>(q)$
385 trees, and all other operations alter only the internal structure of trees.
386
387 As for the $\O(\min(\<rank>(P),\<rank>(Q)))$ part, let us assume for a~while that
388 no dismantling ever takes place and consider the \df{meld forest.} It is a~forest
389 whose leaves correspond to the $n$~single-element heaps constructed by \<Insert>
390 and each internal vertex represents a~heap arisen from melding its sons. The left
391 son will be the one with the greater or equal rank. We therefore want to bound
392 the sum of ranks of all right sons.
393
394 For every right son, we will distribute the change for its rank~$k$ among all leaves
395 in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same
396 rank twice, because the ranks of right sons on every path from the root of the
397 tree to a~leaf are strictly decreasing. (This holds because melding of two heaps
398 always produces a~heap of a~strictly greater rank.) Hence at most~$n/2^k$
399 right sons have rank~$k$ and the total time charged against the leaves is bounded by:
400 $$
401 \sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n.
402 $$
403
404 Let us return dismantling to the game. When a~queue is dismantled, melding the parts
405 back to the heap takes $\O(\<rank>(q))$ time. We can therefore let the dismantling pay for it
406 and omit such induced melds from the meld forest. As the rank of a~heap is never increased
407 by induced melds, the above calculation is still a~proper upper bound on the cost
408 of the regular melds.
409 \qed
410
411 Before we estimate the time spent on deletions, we analyse the refills.
412
413 \lemma
414 Every invocation of the \<Refill> procedure takes time $\O(1)$ amortized.
415
416 \proof
417 When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the
418 queue. This subtree can be split to the ``lossless'' lower part (rank~$r$ and below)
419 and the upper part where list concatenation and thus also corruption takes place. Whenever
420 we visit the lower part during the recursion, we spend at worst $\O(r)$ time there.
421 We will prove that the total time spent in the upper parts during the whole life of the
422 data structure is $\O(n)$. Since each upper vertex can perform at most two calls to the lower
423 part, the total time spent in the lower parts is $\O(rn)$. All this can be prepaid by the
424 inserts.
425
426 Let us focus on the upper part. There are three possibilities of what can happen
427 when we visit a~vertex:
428
429 \itemize\ibull
430
431 \:We delete it: Every vertex deleted has to have been created at some time in the past.
432 New vertices are created only during inserts and melds (when joining two trees) and
433 we have already shown that these operations have constant amortized complexity. Then the
434 same must hold for deletions.
435
436 \:We recurse twice and concatenate the lists: The lists are disassembled only when
437 they reach the root of the tree, otherwise they are only concatenated. We can easily
438 model the situation by a~binary tree forest similar to the meld forest. There are~$n$
439 leaves and every internal vertex has outdegree two, so the total number of concatenations
440 is at most~$n$. Each of them can be performed in constant time as the list is doubly linked.
441
442 \:We recurse only once: This occurs only if the rank is even and the gap between the
443 rank of this vertex and its sons is equal to~1. It therefore cannot happen twice in a~row,
444 thus it is clearly dominated by the cost of the other possibilities.
445
446 \endlist
447 \>The total cost of all steps in the upper part is therefore $\O(n)$.
448 \qed
449
450 We now proceed with examining the \<DeleteMin> operation.
451
452 \lemma\id{shdelmin}%
453 Every \<DeleteMin> takes $\O(1)$ time amortized.
454
455 \proof
456 Aside from refilling, which is $\O(1)$ by the previous lemma, the \<DeleteMin>
457 takes care of the Rank invariant. This happens by checking the length of the leftmost
458 path and dismantling the tree if the length is too far from the tree's rank~$k$.
459 When the invariant is satisfied, the leftmost path is visited by the subsequent
460 call to \<Refill>, so we can account the check on the refilling.
461
462 When we are dismantling, we have to pay $\O(k)$ for the operation itself and
463 another $\O(k)$ for melding the trees back to the heap. Since we have produced at most
464 $k/2$ subtrees of distinct ranks, some subtree of rank $k/2$ or more must be missing.
465 Its master tree contained at least $2^{k/2}$ vertices which are now permanently gone
466 from the data structure, so we can charge the cost against them.
467 A~single vertex can participate in the master trees of several dismantlings, but their
468 ranks are always strictly increasing. By the same argument as in the proof of
469 Lemma \ref{shmeld} (complexity of \<Meld>), each vertex pays $\O(1)$.
470
471 We must not forget that \<DeleteMin> also has to recalculate the suffix minima.
472 In the worst case, it requires touching $k$~trees. Because of the Rank invariant,
473 this is linear in the size of the
474 leftmost path and therefore it can be also paid for by \<Refill>. (Incidentally,
475 this was the only place where we needed the invariant.)
476 \qed
477
478 \<Explode>s are easy not only to implement, but also to analyse:
479
480 \lemma
481 Every \<Explode> takes $\O(1)$ time amortized.
482
483 \proof
484 As all queues, vertices and items examined by \<Explode> are forever gone from the heap,
485 we can charge the constant time spent on each of them against the operations
486 that have created them.
487 \qed
488
489 It remains to take care of the calculation with ranks:
490
491 \lemma\id{shyards}%
492 Every manipulation with ranks performed by the soft heap operations can be
493 implemented on the Pointer Machine in constant amortized time.
494
495 \proof
496 We will recycle the idea of ``yardsticks'' from Section \ref{bucketsort}.
497 We create a~yardstick --- a~doubly linked list whose elements represent the possible
498 values of a~rank. Every vertex of a~queue will store its rank as a~pointer to
499 the corresponding ``tick'' of the yardstick. We will extend the list as necessary.
500
501 Comparison of two ranks for equality is then trivial, as is incrementing or decrementing
502 the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even
503 flag in every tick. This covers all uses of ranks except for the comparisons for inequality
504 when melding. In step~1 of \<Meld>, we just mark the ticks of the two ranks and walk
505 the yardstick from the beginning until we come across a~mark. Thus we compare the ranks
506 in time proportional to the smaller of them, which is the real cost of the meld anyway.
507 The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put
508 to~$P$ are strictly increasing, we can start walking the list at the rank of the previous
509 element in~$P$. The cost is then the difference between the current and the previous rank
510 and their sum telescopes, again to the real cost of the meld.
511 \qed
512
513 Now we can put the bits together and laurel our effort with the following theorem:
514
515 \thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
516 A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
517 a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
518 in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
519 heap contains at most $\varepsilon n$ corrupted items.
520
521 \proof
522 We set the parameter~$r$ to~$2+2\lceil\log (1/\varepsilon)\rceil$. The rest follows
523 from the analysis above. By Lemma \ref{shcorrlemma}, there are always at most $n/2^{r-2}
524 \le \varepsilon n$ corrupted items in the heap. By Lemma \ref{shmeld}--\ref{shyards},
525 the time spent on all operations in the sequence can be paid for by charging $\O(r)$ time
526 against each \<Insert>. This yields the time bound.
527 \qed
528
529 \rem
530 When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any
531 items, so it can be used like any traditional heap. By the standard lower bound on
532 sorting it therefore requires $\Omega(\log n)$ time per operation, so the
533 time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chazelle:softheap}
534 proves that it is optimal for every choice of~$\varepsilon$.
535
536 The space consumed by the heap need not be linear in the \em{current} number
537 of items, but if a~case where this matters ever occurred, we could fix it easily
538 by rebuilding the whole data structure completely after $n/2$ deletes. This
539 increases the number of potentially corrupted items, but at worst twice, so it
540 suffices to decrease~$\varepsilon$ twice.
541
542 %--------------------------------------------------------------------------------
543
544 \section{Robust contractions}
545
546 Having the soft heaps at hand, we would like to use them in a~conventional MST
547 algorithm in place of a~normal heap. The most efficient specimen of a~heap-based
548 algorithm we have seen so far is the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
549 It is based on a~simple, yet powerful idea: Run the Jarn\'\i{}k's algorithm with
550 limited heap size, so that it stops when the neighborhood of the tree becomes too
551 large. Grow multiple such trees, always starting in a~vertex not visited yet. All
552 these trees are contained in the MST, so by the Contraction lemma
553 (\ref{contlemma}) we can contract each of them to a~single vertex and iterate
554 the algorithm on the resulting graph.
555
556 We can try implanting the soft heap in this algorithm, preferably in its earlier
557 version without active edges (\ref{jarnik}) as the soft heap lacks the \<Decrease>
558 operation. This brave, but somewhat simple-minded attempt is however doomed to
559 fail. The reason is of course the corruption of items inside the heap, which
560 leads to increase of weights of some subset of edges. In presence of corrupted
561 edges, most of the theory we have so carefully built breaks down. For example,
562 the Blue lemma (\ref{bluelemma}) now holds only when we consider a~cut with no
563 corrupted edges, with a~possible exception of the lightest edge of the cut.
564 Similarly, the Red lemma (\ref{redlemma}) is true only if the heaviest edge on
565 the cycle is not corrupted.
566
567 There is fortunately some light in this darkness. While the basic structural
568 properties of MST's no longer hold, there is a~weaker form of the Contraction
569 lemma that takes the corrupted edges into account. Before we prove this lemma,
570 we expand our awareness of subgraphs which can be contracted.
571
572 \defn
573 A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,
574 of~$G$'s edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints
575 of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.
576
577 \example\id{jarniscont}%
578 Let us see that when we stop the Jarn\'\i{}k's algorithm at some moment and
579 we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.
580 Indeed, when we consider any two distinct edges $uv, xy$ ($u,x\in C$ and $v,y\not\in C$),
581 they enter the algorithm's heap at some time. Without loss of generality $uv$~is the first.
582 Before the algorithm reaches the vertex~$x$, it adds the whole path $ux$ to the tree.
583 As the edge~$uv$ never leaves the heap, all edges on the path $ux$ must be lighter
584 than this edge.
585
586 We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
587 of contractible subgraphs. We again assume that we are working with multigraphs
588 and that they need not be connected.
589 Furthermore, we slightly abuse the notation in the way that we omit the explicit bijection
590 between $G-C$ and~$G/C$, so we can write $G=C \cup (G/C)$.
591
592 \lemman{Generalized contraction}
593 When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$.
594
595 \proof
596 As both sides of the equality are forests spanning the same graph, it suffices
597 to show that $\msf(G) \subseteq \msf(C)\cup\msf(G/C)$.
598 Let us show that edges of~$G$ that do not belong to the right-hand side
599 do not belong to the left-hand side either.
600 We know that the edges that
601 do not participate in the MSF of some graph are exactly those which are the heaviest
602 on some cycle (this is the Cycle rule from Lemma \ref{redlemma}).
603
604 Whenever an~edge~$g$ lies in~$C$, but not in~$\msf(C)$, then $g$~is the heaviest edge
605 on some cycle in~$C$. As this cycle is also contained in~$G$, the edge $g$~does not participate
606 in $\msf(G)$ either.
607
608 Similarly for $g\in (G/C)\setminus\msf(G/C)$: when the cycle does not contain
609 the vertex~$c$ to which we have contracted the subgraph~$C$, this cycle is present
610 in~$G$, too. Otherwise we consider the edges $e,f$ incident with~$c$ on this cycle.
611 Since $C$~is contractible, there must exist a~path~$P$ in~$C$ connecting the endpoints
612 of~$e$ and~$f$ in~$G$, such that all edges of~$P$ are lighter than either $e$ or~$f$
613 and hence also than~$g$. Expanding~$c$ in the cycle to the path~$P$ then produces
614 a~cycle in~$G$ whose heaviest edge is~$g$.
615 \qed
616
617 We are now ready to bring corruption back to the game and state a~``robust'' version
618 of this lemma. A~notation for corrupted graphs will be handy:
619
620 \nota\id{corrnota}%
621 When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
622 R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of
623 some of the edges in~$R$. As usually, we will assume that all edges of this graph
624 have pairwise distinct weights. While this is technically not true for the corruption
625 caused by soft heaps, we can easily make the weights unique.
626
627 Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with
628 exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$).
629
630 \lemman{Robust contraction, Chazelle \cite{chazelle:almostacker}}\id{robcont}%
631 Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
632 for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.
633
634 \proof
635 We will modify the proof of the previous lemma. We will again consider all possible types
636 of edges which do not belong to the right-hand side and we will show that they are the
637 heaviest edges of certain cycles. Every edge~$g$ of~$G$ lies either in~$C$, or in $H=(G/C)\setminus R^C$,
638 or possibly in~$R^C$.
639
640 If $g\in C\setminus\msf(C)$, then the same argument as before applies.
641
642 If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $g$~is the heaviest.
643 When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are done.
644 Otherwise we observe that the edges $e,f$ adjacent to~$c$ on this cycle cannot be corrupted
645 (they would be in~$R^C$ otherwise, which is impossible). By contractibility of~$C$ there exists
646 a~path~$P$ in~$C\crpt (R\cap C)$ such that all edges of~$P$ are lighter than $e$ or~$f$ and hence
647 also than~$g$. The weights of the edges of~$P$ in the original graph~$G$ cannot be higher than
648 in~$G\crpt R$, so the path~$P$ is lighter than~$g$ even in~$G$ and we can again perform the
649 trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst(G)$.
650 \qed
651
652 \para
653 We still intend to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
654 of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
655 We recursively compute the MSF of that subgraphs and of the contracted graph. Then we take the
656 union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
657 the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
658
659 We can formulate the exact partitioning algorithm and its properties as follows:
660
661 \algn{Partition a~graph to a~collection of contractible clusters}\id{partition}%
662 \algo
663 \algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the clusters,
664   and an~accuracy parameter~$\varepsilon$.
665 \:Mark all vertices as ``live''.
666 \:$\C\=\emptyset$, $R^\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.}
667 \:While there is a~live vertex~$v_0$:
668 \::$T=\{v_0\}$. \cmt{the tree that we currently grow}
669 \::$K=\emptyset$. \cmt{edges known to be corrupted in the current iteration}
670 \::\<Create> a~soft heap with accuracy~$\varepsilon$ and \<Insert> the edges adjacent to~$v_0$ into it.
671 \::While the heap is not empty and $\vert T\vert \le t$:
672 \:::\<DeleteMin> an~edge $uv$ from the heap, assume $u\in T$.
673 \:::If $uv$ was corrupted, add it to~$K$.
674 \:::If $v\in T$, drop the edge and repeat the previous two steps.
675 \:::$T\=T\cup\{v\}$.
676 \:::If $v$ is dead, break out of the current loop.
677 \:::Insert all edges incident with~$v$ to the heap.
678 \::$\C\=\C \cup \{G[T]\}$. \cmt{Record the cluster induced by the tree.}
679 \::\<Explode> the heap and add all remaining corrupted edges to~$K$.
680 \::$R^\C\=R^\C \cup K^T$. \cmt{Record the ``interesting'' corrupted edges.}
681 \::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.}
682 \::Mark all vertices of~$T$ as ``dead''.
683 \algout The collection $\C$ of contractible clusters and the set~$R^\C$ of
684 corrupted edges in the neighborhood of these clusters.
685 \endalgo
686
687 \thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
688 Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
689 and~$t$, the Partition algorithm (\ref{partition}) constructs a~collection
690 $\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that:
691
692 \numlist\ndotted
693 \:All the clusters and the set~$R^\C$ are mutually edge-disjoint.
694 \:Each cluster contains at most~$t$ vertices.
695 \:Each vertex of~$G$ is contained in at least one cluster.
696 \:The connected components of the union of all clusters have at least~$t$ vertices each,
697   except perhaps for those which are equal to a~connected component of $G\setminus R^\C$.
698 \:$\vert R^\C\vert \le 2\varepsilon m$.
699 \:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
700 \:The algorithm runs in time $\O(n+m\log (1/\varepsilon))$.
701 \endlist
702
703 \proof
704 Claim~1: The Partition algorithm grows a~series of trees which induce the clusters~$C_i$ in~$G$.
705 A~tree is built from edges adjacent to live vertices
706 and once it is finished, all vertices of the tree die, so no edge is ever reused in another
707 tree. The edges that enter~$R^\C$ are immediately deleted from the graph, so they never participate
708 in any tree.
709
710 Claim~2: The algorithm stops when all vertices are dead, so each vertex must have
711 entered some tree.
712
713 Claim~3: The trees have at most~$t$ vertices each, which limits the size of the
714 $C_i$'s as well.
715
716 Claim~4: We can show that each connected component has $t$~or more vertices as we already did
717 in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it gathers
718 $t$~vertices, or it joins one of the existing trees (this only increases the
719 size of the component), or the heap becomes empty (which means that the tree spans
720 a~full component of the current graph and hence also of the final~$G\setminus R^\C$).
721
722 Claim~5: The set~$R^\C$ contains a~subset of edges corrupted by the soft heaps over
723 the course of the algorithm. As every edge is inserted to a~heap at most once per
724 its endpoint, the heaps can corrupt at worst $2\varepsilon m$ edges altogether.
725
726 We will prove the remaining two claims as separate lemmata.
727 \qed
728
729 \lemman{Correctness of Partition, Claim 6 of Theorem \ref{partthm}}
730 $$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\biggl( \bigl(G / \bigcup_i C_i \bigr) \setminus R^\C\biggr) \cup R^\C.$$
731
732 \proof
733 By iterating the Robust contraction lemma (\ref{robcont}). Let $K_i$ be the set of edges
734 corrupted when constructing the cluster~$C_i$ in the $i$-th phase of the algorithm,
735 and similarly for the state of the other variables at that time.
736 We will use induction on~$i$ to prove that the lemma holds at the end of every phase.
737
738 At the beginning, the statement is obviously true, even as an~equality.
739 In the $i$-th phase we construct the cluster~$C_i$ by running the partial Jarn\'\i{}k's algorithm on the graph
740 $G_i = G\setminus\bigcup_{j<i} K_{\smash j}^{C_j}$.
741 If it were not for corruption, the cluster~$C_i$ would be contractible, as we already know from Example \ref{jarniscont}.
742 When the edges in~$K_i$ get corrupted, the cluster is contractible in some corrupted graph
743 $G_i \crpt K_i$. (We have to be careful as the edges are becoming corrupted gradually,
744 but it is easy to check that it can only improve the situation.) Since $C_i$~shares no edges
745 with~$C_j$ for any~$j<i$, we know that~$C_i$ also a~contractible subgraph of $(G_i / \bigcup_{j<i} C_j) \crpt K_i$.
746 Now we can use the Robust contraction lemma to show that:
747 $$
748 \msf\biggl(\bigl(G / \bigcup_{j<i} C_j \bigr) \setminus \bigcup_{j<i} K_j^{C_j} \biggr) \subseteq
749 \msf(C_i) \cup \msf\biggl(\bigl(G / \bigcup_{j\le i} C_j \bigr) \setminus \bigcup_{j\le i} K_j^{C_j} \biggr) \cup K_i^{C_i}.
750 $$
751 This completes the induction step, because $K_j^{C_j} = K_j^{\C_j}$ for all~$j$.
752 \qed
753
754 \lemman{Efficiency of Partition, Claim 7 of Theorem \ref{partthm}}
755 The Partition algorithm runs in time $\O(n+m\log(1/\varepsilon))$.
756
757 \proof
758 The inner loop (steps 7--13) processes the edges of the current cluster~$C_i$ and also
759 the edges in its neighborhood $\delta(C_i)$. Steps 6 and~13 insert every such edge to the heap
760 at most once, so steps 8--12 visit each edge also at most once. For every edge, we spend
761 $\O(\log(1/\varepsilon))$ time amortized on inserting it and $\O(1)$ on the other operations
762 (by Theorem \ref{softheap} on performance of the soft heaps).
763
764 Each edge of~$G$ can participate in some $C_i\cup \delta(C_i)$ only twice before both its
765 endpoints die. The inner loop therefore processes $\O(m)$ edges total, so it takes $\O(m\log(1/\varepsilon))$
766 time. The remaining parts of the algorithm spend $\O(m)$ time on operations with clusters and corrupted edges
767 and additionally $\O(n)$ on identifying the live vertices.
768 \qed
769
770 %--------------------------------------------------------------------------------
771
772 \section{Decision trees}
773
774 The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
775 trees constructed by brute force for very small subgraphs. In this section, we will
776 explain the basics of the decision trees and prove several lemmata which will
777 turn out to be useful for the analysis of time complexity of the final algorithm.
778
779 Let us consider all computations of some comparison-based MST algorithm when we
780 run it on a~fixed graph~$G$ with all possible permutations of edge weights.
781 The computations can be described by a~binary tree. The root of the tree corresponds to the first
782 comparison performed by the algorithm and depending to its result, the computation
783 continues either in the left subtree or in the right subtree. There it encounters
784 another comparison and so on, until it arrives to a~leaf of the tree where the
785 spanning tree found by the algorithm is recorded.
786
787 Formally, the decision trees are defined as follows:
788
789 \defnn{Decision trees and their complexity}\id{decdef}%
790 A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
791 are labeled with pairs of $G$'s edges to be compared, each of the two outgoing edges
792 corresponds to one possible result of the comparison.\foot{There are two possible
793 outcomes since there is no reason to compare an~edge with itself and we, as usually,
794 expect that the edge weights are distinct.}
795 Leaves of the tree are labeled with spanning trees of the graph~$G$.
796
797 A~\df{computation} of the decision tree on a~specific permutation of edge weights
798 in~$G$ is a~path from the root to a~leaf such that the outcome of every comparison
799 agrees with the edge weights. The result of the computation is the spanning tree
800 assigned to its final leaf.
801 A~decision tree is \df{correct} iff for every permutation the corresponding
802 computation results in the real MSF of~$G$ with the particular weights.
803
804 The \df{time complexity} of a~decision tree is defined as its depth. It therefore
805 bounds the number of comparisons spent on every path. (It need not be equal since
806 some paths need not correspond to an~actual computation --- the sequence of outcomes
807 on the path could be unsatisfiable.)
808
809 A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
810 among the correct decision trees for the given graph.
811 We will denote an~arbitrary optimal decision tree for~$G$ by~${\cal D}(G)$ and its
812 complexity by~$D(G)$.
813
814 The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~$D(G)$
815 over all graphs~$G$ with $n$~vertices and~$m$ edges.
816
817 \obs
818 Decision trees are the most general comparison-based computation model possible.
819 The only operations which count in the time complexity are the comparisons. All
820 other computation is free, including solving NP-complete problems or having
821 access to an~unlimited source of non-uniform constants. The decision tree
822 complexity is therefore an~obvious lower bound on the time complexity of the
823 problem in all other models.
824
825 The downside is that we do not know any explicit construction of the optimal
826 decision trees, or at least a~non-constructive proof of their complexity.
827 On the other hand, the complexity of any existing comparison-based algorithm
828 can be used as an~upper bound for the decision tree complexity. For example:
829
830 \lemma
831 $D(m,n) \le 4/3 \cdot n^2$.
832
833 \proof
834 Let us count the comparisons performed by the Contractive Bor\o{u}vka's algorithm.
835 (\ref{contbor}), tightening up the constants in its previous analysis in Theorem
836 \ref{contborthm}. In the first iteration, each edge participates in two comparisons
837 (one for each its endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$
838 comparisons. Then the number of vertices drops at least by a~factor of two, so
839 the subsequent iterations spend at most $(n/2)^2, (n/4)^2, \ldots$ comparisons, which sums
840 to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$. Between the phases,
841 we flatten the multigraph to a~simple graph, which also needs some comparisons,
842 but for every such comparison we remove one of the participating edges, which saves
843 at least one comparison in the subsequent phases.
844 \qed
845
846 \para
847 Of course we can get sharper bounds from the better algorithms, but we will first
848 show how to find the optimal trees using brute force. The complexity of the search
849 will be of course enormous, but as we already promised, we will need the optimal
850 trees only for very small subgraphs.
851
852 \lemman{Construction of optimal decision trees}\id{odtconst}%
853 An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
854 the Pointer Machine in time $\O(2^{2^{4n^2}})$.
855
856 \proof
857 We will try all possible decision trees of depth at most $2n^2$
858 (we know from the previous lemma that the desired optimal tree is shallower). We can obtain
859 any such tree by taking the complete binary tree of exactly this depth
860 and labeling its $2\cdot 2^{2n^2}-1$ vertices with comparisons and spanning trees. Those labeled
861 with comparisons become internal vertices of the decision tree, the others
862 become leaves and the parts of the tree below them are removed. There are less
863 than $n^4$ possible comparisons and less than $2^{n^2}$ spanning trees of~$G$,
864 so the number of candidate decision trees is bounded by
865 $(n^4+2^{n^2})^{2^{2n^2+1}} \le 2^{(n^2+1)\cdot 2^{2n^2+1}} \le 2^{2^{2n^2+2}} \le 2^{2^{3n^2}}$.
866
867 We will enumerate the trees in an~arbitrary order, test each of them for correctness and
868 find the shallowest tree among those correct. Testing can be accomplished by running
869 through all possible permutations of edges, each time calculating the MSF using any
870 of the known algorithms and comparing it with the result given by the decision tree.
871 The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
872 and each permutation can be checked in time $\O(\poly(n))$.
873
874 On the Pointer Machine, trees and permutations can be certainly enumerated in time
875 $\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore
876 $\O(2^{2^{3n^2}} \cdot 2^{n^3} \cdot \poly(n)) = \O(2^{2^{4n^2}})$.
877 \qed
878
879 \paran{Basic properties of decision trees}%
880 The following properties will be useful for analysis of algorithms based
881 on precomputed decision trees. We will omit some technical details, referring
882 the reader to section 5.1 of the Pettie's article \cite{pettie:optimal}.
883
884 \lemma\id{dtbasic}%
885 The decision tree complexity $D(m,n)$ of the MSF satisfies:
886 \numlist\ndotted
887 \:$D(m,n) \ge m/2$ for $m,n > 2$.
888 \:$D(m',n') \ge D(m,n)$ whenever $m'\ge m$ and $n'\ge n$.
889 \endlist
890
891 \proof
892 For every $m,n>2$ there is a~graph on $n$~vertices and $m$~edges such that
893 every edge lies on a~cycle. Every correct MSF decision tree for this graph
894 has to compare each edge at least once. Otherwise the decision tree cannot
895 distinguish between the case when an~edge has the lowest of all weights (and
896 thus it is forced to belong to the MSF) and when it has the highest weight (so
897 it is forced out of the MSF).
898
899 Decision trees for graphs on $n'$~vertices can be used for graphs with $n$~vertices
900 as well --- it suffices to add isolated vertices, which does not change the MSF.
901 Similarly, we can increase $m$ to~$m'$ by adding edges parallel to an~existing
902 edge and making them heavier than the rest of the graph, so that they can never
903 belong to the MSF.
904 \qed
905
906 \defn
907 Subgraphs $C_1,\ldots,C_k$ of a~graph~$G$ are called the \df{compartments} of~$G$
908 iff they are edge-disjoint, their union is the whole graph~$G$ and
909 $\msf(G) = \bigcup_i \msf(C_i)$ for every permutation of edge weights.
910
911 \lemma\id{partiscomp}%
912 The clusters $C_1,\ldots,C_k$ generated by the Partition procedure of the
913 previous section (Algorithm \ref{partition}) are compartments of the graph
914 $H=\bigcup_i C_i$.
915
916 \proof
917 The first and second condition of the definition of compartments follow
918 from the Partitioning theorem (\ref{partthm}), so it remains to show that $\msf(H)$
919 is the union of the MSF's of the individual compartments. By the Cycle rule
920 (Lemma \ref{redlemma}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
921 it is the heaviest edge on some cycle. It is therefore sufficient to prove that
922 every cycle in~$H$ is contained within a~single~$C_i$.
923
924 Let us consider a~cycle $K\subseteq H$ and a~cluster~$C_i$ such that it contains
925 an~edge~$e$ of~$K$ and all clusters constructed later by the procedure do not contain
926 any. If $K$~is not fully contained in~$C_i$, we can extend the edge~$e$ to a~maximal
927 path contained in both~$K$ and~$C_i$. Since $C_i$ shares at most one vertex with the
928 earlier clusters, there can be at most one edge from~$K$ adjacent to the maximal path,
929 which is impossible.
930 \qed
931
932 \lemma
933 Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then there exists an~optimal
934 MSF decision tree for~$G$ that does not compare edges of distinct compartments.
935
936 \proofsketch
937 Consider a~subset~$\cal P$ of edge weight permutations~$w$ that satisfy $w(e) < w(f)$
938 whenever $e\in C_i, f\in C_j, i<j$. For such permutations, no decision tree can
939 gain any information on relations between edge weights in a~single compartment by
940 inter-compartment comparisons --- the results of all such comparisons are determined
941 in advance.
942
943 Let us take an~arbitrary correct decision tree for~$G$ and restrict it to
944 vertices reachable by computations on~$\cal P$. Whenever a~vertex contained
945 an~inter-compartment comparison, it has lost one of its sons, so we can remove it
946 by contracting its only outgoing edge. We observe that we get a~decision tree
947 satisfying the desired condition and that this tree is correct.
948
949 As for the correctness, the MSF of a~single~$C_i$ is uniquely determined by
950 comparisons of its weights and the set~$\cal P$ contains all combinations
951 of orderings of weights inside individual compartments. Therefore every
952 spanning tree of every~$C_i$ and thus also of~$H$ is properly recognized.
953 \qed
954
955 \lemma\id{compartsum}%
956 Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then $D(G) = \sum_i D(C_i)$.
957
958 \proofsketch
959 A~collection of decision trees for the individual compartments can be ``glued together''
960 to a~decision tree for~$G$. We take the decision tree for~$C_1$, replace every its leaf
961 by a~copy of the tree for~$C_2$ and so on. Every leaf~$\ell$ of the compound tree will be
962 labeled with the union of labels of the original leaves encountered on the path from
963 the root to~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$.
964
965 The other inequality requires more effort. We use the previous lemma to transform
966 the optimal decision tree for~$G$ to another of the same depth, but without inter-compartment
967 comparisons. Then we prove by induction on~$k$ and then on the depth of the tree
968 that this tree can be re-arranged, so that every computation first compares edges
969 from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed
970 to decision trees for the $C_i$'s. Also, without loss of generality all trees for
971 a~single~$C_i$ can be made isomorphic to~${\cal D}(C_i)$.
972 \qed
973
974 \cor\id{dtpart}%
975 If $C_1,\ldots,C_k$ are the clusters generated by the Partition procedure (Algorithm \ref{partition}),
976 then $D(\bigcup_i C_i) = \sum_i D(C_i)$.
977
978 \proof
979 Lemma \ref{partiscomp} tells us that $C_1,\ldots,C_k$ are compartments of the graph
980 $\bigcup C_i$, so we can apply Lemma \ref{compartsum} on them.
981 \qed
982
983 \cor\id{dttwice}%
984 $2D(m,n) \le D(2m,2n)$ for every $m,n$.
985
986 \proof
987 For an~arbitrary graph~$G$ with $m$~edges and $n$~vertices, we create a~graph~$G_2$
988 consisting of two copies of~$G$ sharing a~single vertex. The copies of~$G$ are obviously
989 compartments of~$G_2$, so by Lemma \ref{compartsum} it holds that $D(G_2) = 2D(G)$.
990 Taking a~maximum over all choices of~$G$ yields $D(2m,2n) \ge \max_G D(G_2) = 2D(m,n)$.
991 \qed
992
993 %--------------------------------------------------------------------------------
994
995 \section{An optimal algorithm}\id{optalgsect}%
996
997 Once we have developed the soft heaps, partitioning and MST decision trees,
998 it is now simple to state the Pettie's and Ramachandran's MST algorithm
999 and prove that it is asymptotically optimal among all MST algorithms in
1000 comparison-based models. Several standard MST algorithms from the previous
1001 chapters will also play their roles.
1002
1003 We will describe the algorithm as a~recursive procedure. When the procedure is
1004 called on a~graph~$G$, it sets the parameter~$t$ to roughly $\log^{(3)} n$ and
1005 it calls the \<Partition> procedure to split the graph into a~collection of
1006 clusters of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision
1007 trees to find the MSF of the clusters. The graph obtained by contracting
1008 the clusters is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's
1009 algorithm runs on it in linear time. Afterwards we combine the MSF's of the clusters
1010 and of the contracted graphs, we mix in the corrupted edges and run two iterations
1011 of the Contractive Bor\o{u}vka's algorithm. This guarantees reduction in the number of
1012 both vertices and edges by a~constant factor, so we can efficiently recurse on the
1013 resulting graph.
1014
1015 \algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
1016 \algo
1017 \algin A~connected graph~$G$ with an~edge comparison oracle.
1018 \:If $G$ has no edges, return an~empty tree.
1019 \:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}
1020 \:Call \<Partition> (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
1021   a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges.
1022 \:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees.
1023 \:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph}
1024 \:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
1025 \:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
1026 \:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
1027   getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
1028 \:$F_C \= \mst(G_C)$ obtained by a~recursive call to this algorithm.
1029 \:Return $F_B \cup F_C$.
1030 \algout The minimum spanning tree of~$G$.
1031 \endalgo
1032
1033 Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm})
1034 and from the proofs of the respective algorithms used as subroutines. Let us take a~look at
1035 the time complexity. We will be careful to use only the operations offered by the Pointer Machine.
1036
1037 \lemma\id{optlemma}%
1038 The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence:
1039 $$
1040 T(m,n) \le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m,
1041 $$
1042 where~$c_1$ and~$c_2$ are some positive constants and $D$~is the decision tree complexity
1043 from the previous section.
1044
1045 \proof
1046 The first two steps of the algorithm are trivial as we have linear time at our
1047 disposal.
1048
1049 By the Partitioning theorem (\ref{partthm}), the call to \<Partition> with~$\varepsilon$
1050 set to a~constant takes $\O(m)$ time and it produces a~collection of clusters of size
1051 at most~$t$ and at most $m/4$ corrupted edges. It also guarantees that the
1052 connected components of the union of the $C_i$'s have at least~$t$ vertices
1053 (unless there is just a~single component).
1054
1055 To apply the decision trees, we will use the framework of topological computations developed
1056 in Section \ref{bucketsort}. We pad all clusters in~$\C$ with isolated vertices, so that they
1057 have exactly~$t$ vertices. We use a~computation that labels the graph with a~pointer to
1058 its optimal decision tree. Then we apply Theorem \ref{topothm} combined with the
1059 brute-force construction of optimal decision trees from Lemma \ref{odtconst}. Together they guarantee
1060 that we can assign the decision trees to the clusters in time:
1061 $$\O\Bigl(\Vert\C\Vert + t^{t(t+2)} \cdot \bigl(2^{2^{4t^2}} + t^2\bigr)\Bigr)
1062 = \O\Bigl(m + 2^{2^{2^t}}\Bigr)
1063 = \O(m).$$
1064 Execution of the decision tree on each cluster~$C_i$ then takes $\O(D(C_i))$ steps.
1065
1066 The contracted graph~$G_A$ has at most $n/t = \O(n / \log^{(3)}n)$ vertices and asymptotically
1067 the same number of edges as~$G$, so according to Corollary \ref{ijdens}, the Iterated Jarn\'\i{}k's
1068 algorithm runs on it in linear time.
1069
1070 The combined graph~$G_B$ has~$n$ vertices, but less than~$n$ edges from the
1071 individual spanning trees and at most~$m/4$ additional edges which were
1072 corrupted. The Bor\o{u}vka steps on~$G_B$ take $\O(m)$
1073 time by Lemma \ref{boruvkaiter} and they produce a~graph~$G_C$ with at most~$n/4$
1074 vertices and at most $n/4 + m/4 \le m/2$ edges. (The $n$~tree edges in~$G_B$ are guaranteed
1075 to be reduced by the Bor\o{u}vka's algorithm.) It is easy to verify that this
1076 graph is still connected, so we can recurse on it.
1077
1078 The remaining steps of the algorithm can be easily performed in linear time either directly
1079 or in case of the contractions by the bucket-sorting techniques of Section \ref{bucketsort}.
1080 \qed
1081
1082 \paran{Optimality}%
1083 The properties of decision tree complexity, which we have proven in the previous
1084 section, will help us show that the time complexity recurrence is satisfied by a~constant
1085 multiple of the decision tree complexity $D(m,n)$ itself. This way, we will prove
1086 the following theorem:
1087
1088 \thmn{Optimality of the Optimal algorithm}
1089 The time complexity of the Optimal MST algorithm \ref{optimal} is $\Theta(D(m,n))$.
1090
1091 \proof
1092 We will prove by induction that $T(m,n) \le cD(m,n)$ for some $c>0$. The base
1093 case is trivial, for the induction step we will expand on the previous lemma:
1094 \def\eqalign#1{\null\,\vcenter{\openup\jot
1095   \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
1096       \crcr#1\crcr}}\,}
1097 $$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
1098 T(m,n)
1099     &\le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m &(Lemma \ref{optlemma})\cr
1100     &\le c_1 D({\textstyle\bigcup}_i C_i) + T(m/2, n/4) + c_2 m &(Corollary \ref{dtpart})\cr
1101     &\le c_1 D(m,n) + T(m/2, n/4) + c_2m &(definition of $D(m,n)$)\cr
1102     &\le c_1 D(m,n) + cD(m/2, n/4) + c_2m &(induction hypothesis)\cr
1103     &\le c_1 D(m,n) + c/2\cdot D(m,n/2) + c_2m &(Corollary \ref{dttwice})\cr
1104     &\le c_1 D(m,n) + c/2\cdot D(m,n) + 2c_2 D(m,n) &(Lemma \ref{dtbasic})\cr
1105     &\le (c_1 + c/2 + 2c_2) \cdot D(m,n)&\cr
1106     &\le cD(m,n). &(by setting $c=2c_1+4c_2$)\cr
1107 }}$$
1108 The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound on
1109 the time complexity of every comparison-based algorithm.
1110 \qed
1111
1112 \paran{Complexity of MST}%
1113 As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem
1114 is still open and so is therefore the time complexity of the optimal algorithm. However,
1115 every time we come up with another comparison-based algorithm, we can use its complexity
1116 (or more specifically the number of comparisons it performs, which can be even lower)
1117 as an~upper bound on the optimal algorithm.
1118
1119 The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$.
1120 It has been discovered by Chazelle \cite{chazelle:ackermann} as an~improvement of his previous
1121 $\O(m\timesalpha(m,n)\cdot\log\alpha(m,n))$ algorithm \cite{chazelle:almostacker}.
1122 It is also based on the ideas of this chapter --- in particular the soft heaps and robust contractions.
1123 The algorithm is very complex and it involves a~lot of elaborate
1124 technical details, so we only refer to the original paper here. Another algorithm of the same
1125 complexity, using similar ideas, has been discovered independently by Pettie \cite{pettie:ackermann}, who,
1126 having the optimal algorithm at hand, does not take care about the low-level details and he only
1127 bounds the number of comparisons. Using any of these results, we can prove an~Ackermannian
1128 upper bound on the optimal algorithm:
1129
1130 \thmn{Upper bound on complexity of the Optimal algorithm}
1131 The time complexity of the Optimal MST algorithm is $\O(m\timesalpha(m,n))$.
1132
1133 \proof
1134 We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Chazelle \cite{chazelle:ackermann}
1135 or Pettie \cite{pettie:ackermann}.
1136 \qed
1137
1138 Similarly to the Iterated Jarn\'\i{}k's algorithm, this bound is actually linear for classes of graphs
1139 that do not have density extremely close to constant:
1140
1141 \cor
1142 The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot a(k,n)$ for any fixed~$k$.
1143
1144 \proof
1145 Combine the previous theorem with Lemma \ref{alphaconst}.
1146 \qed
1147
1148 \rem
1149 It is also known from \cite{pettie:optimal} that when we run the Optimal algorithm on a~random
1150 graph drawn from either $G_{n,p}$ (random graphs on~$n$ vertices, each edge is included with probability~$p$
1151 independently on the other edges) or $G_{n,m}$ (we draw the graph uniformly at random from the
1152 set of all graphs with~$n$ vertices and $m$~edges), it runs in linear time with high probability,
1153 regardless of the edge weights.
1154
1155 \paran{Models of computation}%
1156 Another important consequence of the optimal algorithm is that when we aim for a~linear-time
1157 MST algorithm (or for proving that it does not exist), we do not need to care about computational
1158 models at all. The elaborate RAM data structures of Chapter \ref{ramchap}, which have helped us
1159 so much in the case of integer weights, cannot help if we are allowed to access the edge weights
1160 by performing comparisons only. We can even make use of non-uniform objects given by some sort
1161 of oracle. Indeed, whatever trick we employ to achieve linear time complexity, we can mimic it in the
1162 world of decision trees and thus we can use it to show that the algorithm we already knew is
1163 also linear.
1164
1165 This however applies to deterministic algorithms only --- we have shown that access to a~source
1166 of random bits allows us to compute the MST in expected linear time (the KKT algorithm, \ref{kkt}).
1167 There were attempts to derandomize the KKT algorithm, but so far the best result in this direction
1168 is the randomized algorithm also by Pettie \cite{pettie:minirand} which achieves expected linear time
1169 complexity with only $\O(\log^* n)$ random bits.
1170
1171 \endpart