\input macros.tex
\fi
-\chapter{Approaching Optimality}
+\chapter{Approaching Optimality}\id{optchap}%
-\section{Soft heaps}
+\section{Soft heaps}\id{shsect}%
+
+A~vast majority of MST algorithms that we have encountered so far is based on
+the Tarjan's Blue rule (Lemma \ref{bluelemma}). The rule serves to identify
+edges that belong to the MST, while all other edges are left in the process. This
+unfortunately means that the later stages of computation spend most of
+their time on these edges that never enter the MSF. A~notable exception is the randomized
+algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses
+the Red rule (Lemma \ref{redlemma}) to filter out edges that are guaranteed to stay
+outside the MST, so that the graphs with which the algorithm works get smaller
+with time.
Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}
-have presented algorithms for the MST with worst-case time complexity
-$\O(m\timesalpha(m,n))$. We will devote this chapter to their results
-and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal},
+have presented new deterministic algorithms for the MST which are also based
+on the combination of both rules. They have reached worst-case time complexity
+$\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to their results
+and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal}
which is provably optimal.
At the very heart of all these algorithms lies the \df{soft heap} discovered by
similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
the expense of \df{corrupting} a~fraction of the inserted elements by raising
-their values (the values are however never decreased). This allows for
-an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$.
+their values (the values are however never lowered). This allows for
+a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$.
The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
-moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be
+moment at most~$\varepsilon n$ elements of the $n$~elements inserted can be
corrupted.
-\defnn{Soft heap operations}%
-The soft heap contains distinct elements from a~totally ordered universe and it
+\defnn{Soft heap interface}%
+The \df{soft heap} contains a~set of distinct items from a~totally ordered universe and it
supports the following operations:
\itemize\ibull
-\:$\<Create>(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter,
-\:$\<Insert>(H,x)$ --- insert a~new element~$x$ to the heap~$H$,
-\:$\<Meld>(H_1,H_2)$ --- form a~new soft heap containing the elements stored in two disjoint
- heaps $H_1$ and~$H_2$
- (both heaps must have the same~$\varepsilon$ and they are destroyed in the process),
-\:$\<DeleteMin>(H)$ --- delete the minimum element of the heap~$H$ and return its value
+\:$\<Create>(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$.
+\:$\<Insert>(H,x)$ --- Insert a~new item~$x$ into the heap~$H$.
+\:$\<Meld>(P,Q)$ --- Merge two heaps into one, more precisely move all items of a~heap~$Q$
+ to the heap~$P$, destroying~$Q$ in the process. Both heaps must have the same~$\varepsilon$.
+\:$\<DeleteMin>(H)$ --- Delete the minimum item of the heap~$H$ and return its value
(optionally signalling that the value has been corrupted).
+\:$\<Explode>(H)$ --- Destroy the heap and return a~list of all items contained in it
+ (again optionally marking those corrupted).
\endlist
-\figure{softheap1.eps}{\epsfxsize}{XXXX}
+\>For every item, we will distinguish between its \df{original} value at the time
+of insertion and its \df{current} value in the heap, which is possibly corrupted.
+
+\examplen{Linear-time selection}
+We can use soft heaps to select the median (or generally the $k$-th smallest element)
+of a~sequence. We insert all $n$~elements to a~soft heap with error rate $\varepsilon=1/3$.
+Then we delete the minimum about $n/3$ times and we remember the current value~$x$
+of the last element deleted. This~$x$ is greater or equal than the current
+values of the previously deleted elements and thus also than their original values.
+On the other hand, the current values of the $2n/3$ elements remaining in the heap
+are greater than~$x$ and at most $n/3$ of them are corrupted. Therefore at least $n/3$
+original elements are greater than~$x$ and at least $n/3$ ones are smaller.
+
+This allows us to use the~$x$ as a~pivot in the traditional divide-and-conquer algorithm
+for selection (cf.~Hoare's Quickselect algorithm \cite{hoare:qselect}): We split the
+input elements to three parts: $A$~contains those less than~$x$, $B$~those equal to~$x$
+and $C$~those greater than~$x$. If $k\le\vert A\vert$, the desired element lies in~$A$,
+so we can continue by finding the $k$-th smallest element of~$A$. If $\vert A\vert < k \le \vert
+A\vert + \vert B\vert$, the desired element is $x$~itself. Otherwise, we search for the
+$(k-\vert A\vert-\vert B\vert)$-th smallest element of~$C$. Either way, we have removed
+at least $n/3$ items, so the total time complexity is
+$\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$.
-\figure{softheap2.eps}{\epsfxsize}{XXXX}
+We have obtained a~nice alternative to the standard
+linear-time selection algorithm of Blum \cite{blum:selection}. The same trick can be used
+to select a~good pivot in Quicksort \cite{hoare:qsort}, leading to time complexity $\O(n\log n)$
+in the worst case.
\defnn{Soft queues}
-The soft heap is built from \df{soft queues} (we will omit the adjective soft
+The soft heap is built from \df{soft queues} (we will usually omit the adjective soft
in the rest of this section). Each queue has a~shape of a~binary tree.\foot{%
Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are
somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary
-trees with a~special distribution of values. In fact, we get this exact type of binary
-trees from the natural correspondence between general rooted trees and binary trees
-(as described for example in Knuth's Fundamental Algorithms \cite{knuth:fundalg}).
-Also, the original C~code in the Chazelle's paper uses this representation internally.}
-Each vertex~$v$ of the tree remembers a~linked list $\<list>(v)$ of values. The first value in the list
-is called the \df{controlling key} of the vertex, denoted by $\<ckey>(v)$ and defined to be~$+\infty$ if the
-list is empty. The item list in every left son will be used only temporarily and it
-will be kept empty between operations. Only right sons and the root have their lists
-permanently occupied. (See the picture.)
-
-Each vertex is also assigned its \df{rank,} which is a~non-negative integer $\<rank>(v)$.
-The rank of leaves is always zero, the rank of every internal vertex must be strictly
-greater than the ranks of its sons.
+trees with a~special distribution of values. In fact, the original C~code in the Chazelle's
+paper \cite{chazelle:softheap} uses this representation internally.}
+Each vertex~$v$ of the tree remembers a~doubly-linked list of items. The
+item list in every left son will be used only temporarily and it will be kept
+empty between operations. Only right sons and the root have their lists
+permanently occupied. The left sons will be called \df{white}, the right ones
+\df{black.} (See the picture.)
+
+The first value in every list is called the \df{controlling key} of the vertex,
+denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
+value or we set $\<ckey>(v)=+\infty$. The \<ckey>s obey the standard \df{heap order}
+--- a~\<ckey> of a~parent is always smaller than the \<ckey>s of its sons.
+
+Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
+The ranks of leaves are always zero, the rank of every internal vertex can be
+arbitrary, but it must be strictly greater than the ranks of its sons. We
+define the rank of the whole queue to be equal to the rank of its root vertex and
+similarly for its \<ckey>.
+
+A~queue is called \df{complete} if every two vertices joined by an~edge have rank
+difference exactly one. In other words, it is a~complete binary tree and the
+ranks correspond to vertex heights.
+
+\figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\
+(black vertices contain items, numbers indicate ranks)}}
\obs
-The rank of the root.....
-Complete binary trees.....
-The master tree.....
+The complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are
+black (by induction). Any other queue can be trivially embedded to the complete queue of the same
+rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex
+ranks, colors and the ancestor relation.
+
+The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
+two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
+of the original roots and also its \<ckey>. To preserve the heap order, we will choose
+the son whose \<ckey> is smaller.
+
+Sometimes, we will also need to split a~queue to smaller queues. We will call this operation
+\df{dismantling} the queue and it will happen only in cases when the item list in the root
+is empty. It suffices to remove the leftmost (all white) path going from the root. From
+a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing
+if the original queue was not complete.
+
+\figure{softheap2.eps}{\epsfxsize}{Joining and dismantling of soft queues}
+
+We will now define the real soft heap and the operations on it.
+
+\defn A~\df{soft heap} consists of:
+\itemize\ibull
+\:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks),
+ we will call the first queue the \df{head} of the list, the last queue will be its \df{tail};
+\:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \<ckey>
+of those following it in the list;
+\:a~global parameter~$r$: an~even integer to be set depending on~$\varepsilon$.
+\endlist
+
+\>We will define the \df{rank} of a~heap as the highest of the ranks of its queues
+(that is, the rank of the heap's tail).
+
+The heap always keeps the \df{Rank invariant:} When a~root of any tree has rank~$k$,
+its leftmost path contains at least~$k/2$ vertices.
+
+\paran{Operations on soft heaps}
+
+\em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble
+the heap of the smaller rank and we insert its queues to the other heap.
+If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
+a~single queue of rank~$k+1$ as already described and we propagate the new queue as
+a~\df{carry} to the next iteration. (This is similar to addition of binary numbers.)
+Finally, we have to update the suffix minima by walking the new list backwards
+from the last inserted item.
+
+\em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
+a~single-element heap and melding it to the destination heap.
+
+\algn{Creating a~new soft heap}
+\algo
+\algin The~parameter~$\varepsilon$ (the accuracy of the heap).
+\:Allocate memory for a~new heap structure~$H$.
+\:Initialize the list of queues in~$H$ to an~empty list.
+\:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later).
+\algout A~newly minted soft heap~$H$.
+\endalgo
+
+\algn{Melding of two soft heaps}
+\algo
+\algin Two soft heaps~$P$ and~$Q$.
+\:If $\<rank>(P) < \<rank>(Q)$, exchange the queue lists of~$P$ and~$Q$.
+\:$p\=\<head>(P)$.
+\brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that
+there is an~empty queue of infinite rank there.}
+\:While $Q$ still has some queues:
+\::$q\=\<head>(Q)$.
+\::If $\<rank>(p) < \<rank>(q)$, then $p\=$ the successor of~$p$,
+\::else if $\<rank>(p) > \<rank>(q)$, remove~$q$ from~$Q$ and insert it to~$P$ before~$p$,
+\::otherwise (the ranks are equal, we need to propagate the carry):
+\:::$\<carry>\=p$.
+\:::Remove~$p$ from~$P$ and set $p\=$ the original successor of~$p$.
+\:::While $\<rank>(q)=\<rank>(\<carry>)$:
+\::::Remove~$q$ from~$Q$.
+\::::$\<carry>\=\<join>(q, \<carry>)$.
+\::::$q\=\<head>(Q)$.
+\:::Insert~\<carry> before~$q$.
+\:Update the suffix minima: Walk with~$p$ backwards to the head of~$P$:
+\::$p'\=\<suffix\_min>$ of the successor of~$p$.
+\::If $\<ckey>(p) < \<ckey>(p')$, set $\<suffix\_min>(p)\=p$.
+\::Otherwise set $\<suffix\_min>(p)\=p'$.
+\:Destroy the heap~$Q$.
+\algout The merged heap~$P$.
+\endalgo
+
+\algn{Insertion of an~element to a~soft heap}
+\algo
+\algin A~heap~$H$ and a~new element~$x$.
+\:Create a~new heap~$H'$ of the same parameters as~$H$. Let~$H'$ contain a~sole queue of rank~0,
+ whose only vertex has the element~$x$ in its item list.
+\:$\<Meld>(H,H')$.
+\algout An~updated heap~$H$.
+\endalgo
+
+\paran{Corruption}%
+So far, the mechanics of the soft heaps were almost identical to the binomial heaps
+and the reader could rightfully yawn. The things are going to get interesting
+now as we approach the parts where corruption of items takes place.
+
+If all item lists contain at most one item equal to the \<ckey> of the particular
+vertex, no information is lost and the heap order guarantees that the minimum item
+of every queue stays in its root. We can however allow longer lists and let the items
+stored in a~single list travel together between the vertices of the tree, still
+represented by a~common \<ckey>. This data-structural analogue of car pooling will
+allow the items to travel at a~faster rate, but as only a~single item can be equal
+to the \<ckey>, all other items will be inevitably corrupted.
+
+We of course have to be careful about the size of the lists, because we must avoid corrupting
+too many items. We will control the growth according to the vertex ranks. Vertices
+with rank at most~$r$ will always contain just a~single item. Above this level,
+the higher is the rank, the longer list will be allowed.
+
+\para
+\em{Deletion of minimum} will be based on this principle. The minimum is easy to locate
+--- we follow the \<suffix\_min> of the head of the heap to the queue with the minimum
+\<ckey>. There we look inside the item list of the root of the queue. We remove the \em{last}
+item from the list (we do not want the \<ckey> to change) and we return it as the minimum.
+(It is not necessarily the real minimum of all items, but always the minimum of their
+current, possibly corrupted values.)
+
+If the list becomes empty, we \em{refill} it with items from the lower levels of the
+same queue. This process can be best described recursively: We ask the left son to refill itself
+(remember that the left son is always white, so there are currently no items there). If the new
+\<ckey> of the left son is smaller than of the right son, we immediately move the left
+son's list to its parent. Otherwise, we exchange the sons and move the list from the
+new left son to the parent. This way we obey the heap order and at the same time we keep
+the white left son free of items.
+\looseness=1 %%HACK%%
+
+Occasionally, we repeat this process once again and we concatenate the resulting lists
+(we append the latter list to the former, using the smaller of the two \<ckey>s). This
+makes the lists grow longer and we want to do that roughly on every other level of the
+tree. The exact condition will be that either the rank of the current vertex is odd,
+or the difference in ranks between this vertex and its right son is at least two.
+
+If refilling of the left son fails because there are no more items in that subtree
+(we report this by setting the \<ckey> to $+\infty$), the current vertex is no longer
+needed --- the items would just pass through it unmodified. We therefore want to
+remove it. Instead of deleting it directly, we rather make it point to its former
+grandsons and we remove the (now orphaned) original son. This helps us to ensure
+that both sons always keep the same rank, which will be useful for the analysis.
+
+When the refilling is over, we update the suffix minima by walking from the current
+queue to the head of the heap exactly as we did in the \<Meld> procedure.
+
+Our only remaining worry is that the Rank invariant can be broken after the
+refilling. When the leftmost path of the tree becomes too short, we just
+\em{dismantle} the tree as already described and we meld the new trees back to
+the heap. This is easier to handle when the item list at the root vertex is
+empty. We will therefore move this check before the refilling of the root list.
+It will turn out that we have enough time to always walk the leftmost path
+completely, so no explicit counters are needed.
+
+%%HACK%%
+\>Let us translate these ideas to real (pseudo)code:
+
+\algn{Deleting the minimum item from a~soft heap}
+\algo
+\algin A~soft heap~$H$.
+\:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
+\:Remove the final element~$x$ of the item list in the root of~$q$.
+\:If the item list became empty:
+\::Count the vertices on the leftmost path of~$q$.
+\::If there are less than $\<rank>(q)$ of them:
+\:::Remove~$q$ from the list of queues.
+\:::Recalculate the suffix minima as in the \<Meld> procedure.
+\:::Dismantle~$q$ and create a~heap~$H'$ holding the resulting trees.
+\:::Meld them back: $\<Meld>(H,H')$.
+\::Otherwise:
+\:::Call \<Refill> on the root of~$q$.
+\:::If $\<ckey>(q)=+\infty$ (no items left), remove the tree~$q$ from~$H$.
+\:::Recalculate the suffix minima.
+\algout The deleted minimum item~$x$ (possibly corrupted).
+\endalgo
+
+\algn{Refilling the item list of a~vertex}
+\algo
+\algin A~soft queue and its vertex~$v$ with an~empty item list.
+\:Handle trivial cases: If~$v$ has no children or both have $\<ckey>=+\infty$,
+ set $\<ckey>(v)$ to~$+\infty$ and return.
+\:Let \<left> and~\<right> denote the respective sons of~$v$.
+\:Recurse: call $\<Refill>(\<left>)$.
+\:If $\<ckey>(\<left>) > \<ckey>(\<right>)$, swap the sons.
+\:Move the item list from \<left> to~$v$ (implying $\<ckey>(v)=\<ckey>(\<left>)$).
+\:If $\<rank>(v) > r$ and either $\<rank>(v)$ is odd or $\<rank>(v) > \<rank>(\<right>)+1$, recurse once more:
+\::Repeat steps 3--4.
+\::Append the item list from \<left> to the item list at~$v$.
+\:Clean up. If $\<ckey>(\<right>) = +\infty$:
+\::If $\<ckey>(\<left>) = +\infty$, unlink and discard both sons.
+\::Otherwise relink the sons of \<left> to~$v$ and discard \<left>.
+\algout A~modified soft queue.
+\endalgo
+
+\para
+\<Explode> is trivial once we know how to recognize the corrupted items. It simply examines
+all queues in the heap, walks the trees and the item lists of all vertices. It records
+all items seen, the corrupted ones are those that different from their \<ckey>.
+
+\paran{Analysis of accuracy}%
+The description of the operations is now complete, so let us analyse their behavior
+and verify that we have delivered what we promised --- first the accuracy of
+the structure, then the time complexity of operations. In the whole analysis,
+we will denote the total number of elements inserted during the history of the
+structure by~$n$. We will also frequently take advantage of knowing that the
+threshold~$r$ is even.
+
+We start by bounding the sizes of the item lists.
+
+\lemma
+For every vertex~$v$ of a~soft queue, the size $\ell(v)$ of its item list
+satisfies:
+$$\ell(v) \le \max(1, 2^{\lceil \<rank>(v)/2 \rceil - r/2}).$$
+
+\proof
+Initially, all item lists contain at most one item, so the inequality trivially
+holds. Let us continue by induction. Melds can affect the inequality only in the favorable
+direction (they occasionally move an~item list to a~vertex of a~higher rank)
+and so do deletes (they only remove items from lists). The only potentially
+dangerous place is the \<Refill> procedure.
+
+Refilling sometimes just moves items upwards, which is safe, and sometimes it
+joins two lists into one, which generally is not. When $\<rank>(v) \le r$,
+no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either
+$\<rank>(v)$ is odd or $\<rank>(w) < \<rank>(v)-1$ for any son~$w$ of~$v$ (remember
+that both sons have the same rank). In both cases, $\lceil\<rank>(w)/2\rceil \le
+\lceil\<rank>(v)/2\rceil - 1$. By the induction hypothesis, the size of each
+of the two lists being joined is at most $2^{\max(1,\lceil\<rank>(v)/2\rceil - 1 - r/2)}$,
+so the new list has at most $2^{\lceil\<rank>(v)/2\rceil - r/2}$ items. (The maximum
+has disappeared since $\<rank>(v)>r$ and therefore the desired bound is at least~2.)
+\qed
+
+We will now sum the sizes of the lists over all vertices containing corrupted items.
+
+\lemma\id{shcorrlemma}%
+At any given time, the heap contains at most~$n/2^{r-2}$ corrupted items.
+
+\proof
+We first prove an~auxiliary claim: The master trees of all queues contain at most~$n$
+black vertices. This follows by induction: If no deletions have taken place,
+there are exactly~$n$ black vertices, because insertion adds one black vertex and
+melding preserves their number. A~deletion affects the master trees only when
+dismantling takes place and then it only removes a~black vertex.
+
+An~obvious upper bound on the number of corrupted items is the total size of item
+lists in all vertices of rank greater than~$r$. We already know from the previous
+lemma that the list sizes are limited by a~function of the ranks. A~complete tree
+is obviously the worst case, so we will prove that this lemma holds for the master
+tree of every queue in the heap. The actual trees can be much sparser, but the
+above claim guarantees that the total size of the master trees is bounded by the
+number of insertions properly.
+
+So let us consider a~complete tree of~rank~$k$. It has exactly $2^{k-i}$ vertices
+of rank~$i$ and each such vertex contains a~list of at most~$2^{\lceil i/2\rceil - r/2}$
+items by the previous lemma. Summing over all ranks greater than~$r$, we get that
+the total number of corrupted items in this tree is at most:
+$$
+\sum_{i=r+1}^k 2^{k-i}\cdot 2^{\lceil i/2\rceil - r/2}
+= 2^{k-r/2} \cdot \sum_{i=r+1}^k 2^{\lceil i/2\rceil - i}
+\le 2^{k-r/2+1/2} \cdot \sum_{i=r+1}^k 2^{-i/2}
+\le 2^{k-r} \cdot \sum_{i=0}^\infty 2^{-i/2}.
+$$
+The sum of a~geometric series with quotient $2^{-1/2}$ is less than four, so the
+last expression is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ black vertices,
+this makes less than $n_k/2^{r-2}$ corrupted items as we asserted.
+\qed
+
+\paran{Analysis of time complexity}%
+Now we will examine the amortized time complexity of the individual operations.
+We will show that if we charge $\O(r)$ time against every element inserted, it is enough
+to cover the cost of all other operations.
+
+All heap operations use only pointer operations, so it will be easy to derive the time
+bound in the Pointer Machine model. The notable exception is however that the procedures
+often refer to the ranks, which are integers on the order of $\log n$, so they cannot
+fit in a~single memory cell. For the time being, we will assume that the ranks can
+be manipulated in constant time, postponing the proof for later.
+
+We take a~look at the melds first.
+
+\lemma\id{shmeld}%
+The amortized cost of a~meld is $\O(1)$, except for melds induced by dismantling
+which take $\O(\<rank>(q))$, where $q$~is the queue to be dismantled.
+
+\proof
+The real cost of a~meld of heaps $P$ and~$Q$ is linear in the smaller of
+their ranks, plus the time spent on carry propagation. The latter is easy to
+dispose of: Every time there is a~carry, the total number of trees in all
+heaps decreases by one. So it suffices to charge $\O(1)$ against creation of
+a~tree. An~insert creates one tree, dismantling creates at most $\<rank>(q)$
+trees, and all other operations alter only the internal structure of trees.
+
+As for the $\O(\min(\<rank>(P),\<rank>(Q)))$ part, let us assume for a~while that
+no dismantling ever takes place and consider the \df{meld forest.} It is a~forest
+whose leaves correspond to the $n$~single-element heaps constructed by \<Insert>
+and each internal vertex represents a~heap arisen from melding its sons. The left
+son will be the one with the greater or equal rank. We therefore want to bound
+the sum of ranks of all right sons.
+
+For every right son, we will distribute the charge for its rank~$k$ among all leaves
+in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same
+rank twice, because the ranks of right sons on every path from the root of the
+tree to a~leaf are strictly decreasing. (This holds because melding of two heaps
+always produces a~heap of a~rank strictly greater than the smaller of the input ranks.) Hence at most~$n/2^k$
+right sons have rank~$k$ and the total time charged against the leaves is bounded by:
+$$
+\sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n.
+$$
+
+Let us return dismantling to the game. When a~queue is dismantled, melding the parts
+back to the heap takes $\O(\<rank>(q))$ time. We can therefore let the dismantling pay for it
+and omit such induced melds from the meld forest. As the rank of a~heap is never increased
+by induced melds, the above calculation is still a~proper upper bound on the cost
+of the regular melds.
+\qed
+
+Before we estimate the time spent on deletions, we analyse the refills.
+
+\lemma
+Every invocation of \<Refill> takes time $\O(1)$ amortized.
+
+\proof
+When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the
+queue. This subtree can be split to the ``lossless'' lower part (rank~$r$ and below)
+and the upper part where list concatenation and thus also corruption takes place. Whenever
+we visit the lower part during the recursion, we spend at worst $\O(r)$ time there.
+We will prove that the total time spent in the upper parts during the whole life of the
+data structure is $\O(n)$. Since each upper vertex can perform at most two calls to the lower
+part, the total time spent in the lower parts is $\O(rn)$. All this can be prepaid by the
+inserts.
+
+Let us focus on the upper part. There are three possibilities of what can happen
+when we visit a~vertex:
+
+\itemize\ibull
+
+\:We delete it: Every vertex deleted has to have been created at some time in the past.
+New vertices are created only during inserts and melds (when joining two trees) and
+we have already shown that these operations have constant amortized complexity. Then the
+same must hold for deletions.
+
+\:We recurse twice and concatenate the lists: The lists are disassembled only when
+they reach the root of the tree, otherwise they are only concatenated. We can easily
+model the situation by a~binary tree forest similar to the meld forest. There are~$n$
+leaves and every internal vertex has outdegree two, so the total number of concatenations
+is at most~$n$. Each of them can be performed in constant time as the list is doubly linked.
+
+\:We recurse only once: This occurs only if the rank is even and the gap between the
+rank of this vertex and its sons is equal to~1. It therefore cannot happen twice in a~row,
+thus it is clearly dominated by the cost of the other possibilities.
+
+\endlist
+\>The total cost of all steps in the upper part is therefore $\O(n)$.
+\qed
+
+We now proceed with examining the \<DeleteMin> operation.
+
+\lemma\id{shdelmin}%
+Every \<DeleteMin> takes $\O(1)$ time amortized.
+
+\proof
+Aside from refilling, which is $\O(1)$ by the previous lemma, the \<DeleteMin>
+takes care of the Rank invariant. This happens by checking the length of the leftmost
+path and dismantling the tree if the length is too far from the tree's rank~$k$.
+When the invariant is satisfied, the leftmost path is visited by the subsequent
+call to \<Refill>, so we can account the check on the refilling.
+
+When we are dismantling, we have to pay $\O(k)$ for the operation itself and
+another $\O(k)$ for melding the trees back to the heap. Since we have produced at most
+$k/2$ subtrees of distinct ranks, some subtree of rank $k/2$ or more must be missing.
+Its master tree contained at least $2^{k/2}$ vertices which are now permanently gone
+from the data structure, so we can charge the cost against them.
+A~single vertex can participate in the master trees of several dismantlings, but their
+ranks are always strictly increasing. By the same argument as in the proof of
+Lemma \ref{shmeld} (complexity of \<Meld>), each vertex pays $\O(1)$.
+
+We must not forget that \<DeleteMin> also has to recalculate the suffix minima.
+In the worst case, it requires touching $k$~trees. Because of the Rank invariant,
+this is linear in the size of the
+leftmost path and therefore it can be also paid for by \<Refill>. (Incidentally,
+this was the only place where we needed the invariant.)
+\qed
+
+\<Explode>s are easy not only to implement, but also to analyse:
+
+\lemma
+Every \<Explode> takes $\O(1)$ time amortized.
+
+\proof
+As all queues, vertices and items examined by \<Explode> are forever gone from the heap,
+we can charge the constant time spent on each of them against the operations
+that have created them.
+\qed
+
+%%HACK%%
+\>It remains to take care of the calculation with ranks:
+
+\lemma\id{shyards}%
+Every manipulation with ranks performed by the soft heap operations can be
+implemented on the Pointer Machine in constant amortized time.
+
+\proof
+We will recycle the idea of ``yardsticks'' from Section \ref{bucketsort}.
+We create a~yardstick --- a~doubly linked list whose elements represent the possible
+values of a~rank. Every vertex of a~queue will store its rank as a~pointer to
+the corresponding ``tick'' of the yardstick. We will extend the list whenever necessary.
+
+Comparison of two ranks for equality is then trivial, as is incrementing or decrementing
+the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even
+flag in every tick. This covers all uses of ranks except for the comparisons for inequality
+when melding. In step~1 of \<Meld>, we just mark the ticks of the two ranks and walk
+the yardstick from the beginning until we come across a~mark. Thus we compare the ranks
+in time proportional to the smaller of them, which is the real cost of the meld anyway.
+The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put
+to~$P$ are strictly increasing, we can start walking the list at the rank of the previous
+element in~$P$. The cost is then the difference between the current and the previous rank
+and the sum of these differences telescopes, again to the real cost of the meld.
+\qed
+
+We can put the bits together now and laurel our effort with the following theorem:
+
+\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
+A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
+a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
+in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
+heap contains at most $\varepsilon n$ corrupted items.
+
+\proof
+We set the parameter~$r$ to~$2+2\lceil\log (1/\varepsilon)\rceil$. The rest follows
+from the analysis above. By Lemma \ref{shcorrlemma}, there are always at most $n/2^{r-2}
+\le \varepsilon n$ corrupted items in the heap. By Lemma \ref{shmeld}--\ref{shyards},
+the time spent on all operations in the sequence can be paid for by charging $\O(r)$ time
+against each \<Insert>. This yields the time bound.
+\qed
+
+\rem
+When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any
+items, so it can be used like any traditional heap. By the standard lower bound on
+sorting it therefore requires $\Omega(\log n)$ time per operation, so the
+time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chazelle:softheap}
+proves that it is optimal for every choice of~$\varepsilon$.
+
+The space consumed by the heap need not be linear in the \em{current} number
+of items, but if a~case where this matters ever occurred, we could fix it easily
+by rebuilding the whole data structure completely after $n/2$ deletes. This
+increases the number of potentially corrupted items, but at worst twice, so it
+suffices to decrease~$\varepsilon$ twice.
+
+%--------------------------------------------------------------------------------
+
+\section{Robust contractions}
+
+Having the soft heaps at hand, we would like to use them in a~conventional MST
+algorithm in place of a~normal heap. The most efficient specimen of a~heap-based
+algorithm we have seen so far is the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
+It is based on a~simple, yet powerful idea: Run the Jarn\'\i{}k's algorithm with
+limited heap size, so that it stops when the neighborhood of the tree becomes too
+large. Grow multiple such trees, always starting in a~vertex not visited yet. All
+these trees are contained in the MST, so by the Contraction lemma
+(\ref{contlemma}) we can contract each of them to a~single vertex and iterate
+the algorithm on the resulting graph.
+
+We can try implanting the soft heap in this algorithm, preferably in the earlier
+version without active edges (\ref{jarnik}) as the soft heap lacks the \<Decrease>
+operation. This brave, but somewhat simple-minded attempt is however doomed to
+fail. The reason is of course the corruption of items inside the heap, which
+leads to increase of weights of some subset of edges. In presence of corrupted
+edges, most of the theory we have so carefully built breaks down. For example,
+the Blue lemma (\ref{bluelemma}) now holds only when we consider a~cut with no
+corrupted edges, with a~possible exception of the lightest edge of the cut.
+Similarly, the Red lemma (\ref{redlemma}) is true only if the heaviest edge on
+the cycle is not corrupted.
+
+There is fortunately some light in this darkness. While the basic structural
+properties of MST's no longer hold, there is a~weaker form of the Contraction
+lemma that takes the corrupted edges into account. Before we prove this lemma,
+we expand our awareness of subgraphs which can be contracted.
+
+\defn
+A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,
+of~$G$'s edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints
+of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.
+
+\example\id{jarniscont}%
+Let us see that when we stop the Jarn\'\i{}k's algorithm at some moment and
+we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.
+Indeed, when we consider any two distinct edges $uv, xy$ having exactly one endpoint in~$C$
+(w.l.o.g.~$u,x\in C$ and $v,y\not\in C$),
+they enter the algorithm's heap at some time. Without loss of generality $uv$~enters it earlier.
+Before the algorithm reaches the vertex~$x$, it adds the whole path $ux$ to the tree.
+As the edge~$uv$ never leaves the heap, all edges on the path $ux$ must be lighter
+than this edge.
+
+We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
+of contractible subgraphs. We again assume that we are working with multigraphs
+and that they need not be connected.
+Furthermore, we slightly abuse the notation in the way that we omit the explicit bijection
+between $G-C$ and~$G/C$, so we can write $G=C \cup (G/C)$.
+
+\lemman{Generalized contraction}
+When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$.
+
+\proof
+As both sides of the equality are forests spanning the same graph, it suffices
+to show that $\msf(G) \subseteq \msf(C)\cup\msf(G/C)$.
+Let us show that edges of~$G$ that do not belong to the right-hand side
+do not belong to the left-hand side either.
+We know that the edges that
+do not participate in the MSF of some graph are exactly those which are the heaviest
+on some cycle (this is the Cycle rule from Lemma \ref{redlemma}).
+
+Whenever an~edge~$g$ lies in~$C$, but not in~$\msf(C)$, then $g$~is the heaviest edge
+on some cycle in~$C$. As this cycle is also contained in~$G$, the edge $g$~does not participate
+in $\msf(G)$ either.
+
+Similarly for $g\in (G/C)\setminus\msf(G/C)$: when the cycle does not contain
+the vertex~$c$ to which we have contracted the subgraph~$C$, this cycle is present
+in~$G$, too. Otherwise we consider the edges $e,f$ incident with~$c$ on this cycle.
+Since $C$~is contractible, there must exist a~path~$P$ in~$C$ connecting the endpoints
+of~$e$ and~$f$ in~$G$, such that all edges of~$P$ are lighter than either $e$ or~$f$
+and hence also than~$g$. Expanding~$c$ in the cycle to the path~$P$ then produces
+a~cycle in~$G$ whose heaviest edge is~$g$.
+\qed
+
+We are now ready to bring corruption back to the game and state a~``robust'' version
+of this lemma. A~notation for corrupted graphs will be handy:
+
+\nota\id{corrnota}%
+When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
+R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of
+some of the edges in~$R$. As usually, we will assume that all edges of this graph
+have pairwise distinct weights. While this is technically not true for the corruption
+caused by soft heaps, we can easily make it so.
+
+Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with
+exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$).
+
+\lemman{Robust contraction, Chazelle \cite{chazelle:almostacker}}\id{robcont}%
+Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
+for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.
+
+\proof
+We will modify the proof of the previous lemma. We will again consider all possible types
+of edges that do not belong to the right-hand side and we will show that they are the
+heaviest edges of certain cycles. Every edge~$g$ of~$G$ lies either in~$C$, or in $H=(G/C)\setminus R^C$,
+or possibly in~$R^C$.
+
+If $g\in C\setminus\msf(C)$, then the same argument as before applies.
+
+If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $g$~is the heaviest.
+When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are done.
+Otherwise we observe that the edges $e,f$ adjacent to~$c$ on this cycle cannot be corrupted
+(they would be in~$R^C$ otherwise, which is impossible). By contractibility of~$C$ there exists
+a~path~$P$ in~$C\crpt (R\cap C)$ such that all edges of~$P$ are lighter than $e$~or~$f$ and hence
+also than~$g$. The weights of the edges of~$P$ in the original graph~$G$ cannot be higher than
+in~$G\crpt R$, so the path~$P$ is lighter than~$g$ even in~$G$ and we can again perform the
+trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst(G)$.
+\qed
+
+\para
+We still intend to mimic the Iterated Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
+of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
+We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the
+union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
+the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
+
+%%HACK%%
+\>We can formulate the exact partitioning algorithm and its properties as follows:
+
+\algn{Partition a~graph to a~collection of contractible clusters}\id{partition}%
+\algo
+\algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the clusters,
+ and an~accuracy parameter~$\varepsilon$.
+\:Mark all vertices as ``live''.
+\:$\C\=\emptyset$, $R^\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.}
+\:While there is a~live vertex~$v_0$:
+\::$T=\{v_0\}$. \cmt{the tree that we currently grow}
+\::$K=\emptyset$. \cmt{edges known to be corrupted in the current iteration}
+\::\<Create> a~soft heap with accuracy~$\varepsilon$ and \<Insert> the edges adjacent to~$v_0$ into it.
+\::While the heap is not empty and $\vert T\vert \le t$:
+\:::\<DeleteMin> an~edge $uv$ from the heap, assume $u\in T$.
+\:::If $uv$ was corrupted, add it to~$K$.
+\:::If $v\in T$, drop the edge and repeat the previous two steps.
+\:::$T\=T\cup\{v\}$.
+\:::If $v$ is dead, break out of the current loop.
+\:::Insert all edges incident with~$v$ to the heap.
+\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the cluster induced by the tree.}
+\::\<Explode> the heap and add all remaining corrupted edges to~$K$.
+\::$R^\C\=R^\C \cup K^T$. \cmt{Record the ``interesting'' corrupted edges.}
+\::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.}
+\::Mark all vertices of~$T$ as ``dead''.
+\algout The collection $\C$ of contractible clusters and the set~$R^\C$ of
+corrupted edges in the neighborhood of these clusters.
+\endalgo
+
+\thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
+Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
+and~$t$, the Partition algorithm (\ref{partition}) constructs a~collection
+$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that:
+
+\numlist\ndotted
+\:All the clusters and the set~$R^\C$ are mutually edge-disjoint.
+\:Each cluster contains at most~$t$ vertices.
+\:Each vertex of~$G$ is contained in at least one cluster.
+\:The connected components of the union of all clusters have at least~$t$ vertices each,
+ except perhaps for those which are equal to a~connected component of $G\setminus R^\C$.
+\:$\vert R^\C\vert \le 2\varepsilon m$.
+\:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
+\:The algorithm runs in time $\O(n+m\log (1/\varepsilon))$.
+\endlist
+
+\proof
+Claim~1: The Partition algorithm grows a~series of trees which induce the clusters~$C_i$ in~$G$.
+A~tree is built from edges adjacent to live vertices
+and once it is finished, all vertices of the tree die, so no edge is ever reused in another
+tree. The edges that enter~$R^\C$ are immediately deleted from the graph, so they never participate
+in any tree.
+
+Claim~2: The algorithm stops when all vertices are dead, so each vertex must have
+entered some tree.
+
+Claim~3: The trees have at most~$t$ vertices each, which limits the size of the
+$C_i$'s as well.
+
+Claim~4: We can show that each connected component has $t$~or more vertices as we already did
+in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it acquires
+$t$~vertices, or it joins one of the existing trees (this only increases the
+size of the component), or the heap becomes empty (which means that the tree spans
+a~full component of the current graph and hence also of the final~$G\setminus R^\C$).
+
+Claim~5: The set~$R^\C$ contains a~subset of edges corrupted by the soft heaps over
+the course of the algorithm. As every edge is inserted to a~heap at most once per
+its endpoint, the heaps can corrupt at worst $2\varepsilon m$ edges altogether.
+
+We will prove the remaining two claims as separate lemmata.
+\qed
+
+\lemman{Correctness of Partition, Claim 6 of Theorem \ref{partthm}}
+$$\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.$$
+
+\proof
+By iterating the Robust contraction lemma (\ref{robcont}). Let $K_i$ be the set of edges
+corrupted when constructing the cluster~$C_i$ in the $i$-th phase of the algorithm,
+and similarly for the state of the other variables at that time.
+We will use induction on~$i$ to prove that the lemma holds at the end of every phase.
+
+At the beginning, the statement is obviously true, even as an~equality.
+In the $i$-th phase we construct the cluster~$C_i$ by running the partial Jarn\'\i{}k's algorithm on the graph
+$G_i = G\setminus\bigcup_{j<i} K_{\smash j}^{C_j}$.
+If it were not for corruption, the cluster~$C_i$ would be contractible, as we already know from Example \ref{jarniscont}.
+When the edges in~$K_i$ get corrupted, the cluster is contractible in some corrupted graph
+$G_i \crpt K_i$. (We have to be careful as the edges are becoming corrupted gradually,
+but it is easy to check that it can only improve the situation.) Since $C_i$~shares no edges
+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$.
+Now we can use the Robust contraction lemma to show that:
+$$
+\msf\biggl(\bigl(G / \bigcup_{j<i} C_j \bigr) \setminus \bigcup_{j<i} K_j^{C_j} \biggr) \subseteq
+\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}.
+$$
+This completes the induction step, because $K_j^{C_j} = K_j^{\C_j}$ for all~$j$.
+\qed
+
+\lemman{Efficiency of Partition, Claim 7 of Theorem \ref{partthm}}
+The Partition algorithm runs in time $\O(n+m\log(1/\varepsilon))$.
+
+\proof
+The inner loop (steps 7--13) processes the edges of the current cluster~$C_i$ and also
+the edges in its neighborhood $\delta(C_i)$. Steps 6 and~13 insert every such edge to the heap
+at most once, so steps 8--12 visit each edge also at most once. For every edge, we spend
+$\O(\log(1/\varepsilon))$ time amortized on inserting it and $\O(1)$ on the other operations
+(by Theorem \ref{softheap} on performance of the soft heaps).
+
+Each edge of~$G$ can participate in some $C_i\cup \delta(C_i)$ only twice before both its
+endpoints die. The inner loop therefore processes $\O(m)$ edges total, so it takes $\O(m\log(1/\varepsilon))$
+time. The remaining parts of the algorithm spend $\O(m)$ time on operations with clusters and corrupted edges
+and additionally $\O(n)$ on identifying the live vertices.
+\qed
+
+%--------------------------------------------------------------------------------
+
+\section{Decision trees}\id{dtsect}%
+
+The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
+trees constructed by brute force for very small subgraphs. In this section, we will
+explain the basics of the decision trees and prove several lemmata which will
+turn out to be useful for the analysis of time complexity of the final algorithm.
+
+Let us consider all computations of some comparison-based MST algorithm when we
+run it on a~fixed graph~$G$ with all possible permutations of edge weights.
+The computations can be described by a~binary tree. The root of the tree corresponds to the first
+comparison performed by the algorithm and depending to its result, the computation
+continues either in the left subtree or in the right subtree. There it encounters
+another comparison and so on, until it arrives to a~leaf of the tree where the
+spanning tree found by the algorithm is recorded.
+
+Formally, the decision trees are defined as follows:
+
+\defnn{Decision trees and their complexity}\id{decdef}%
+A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
+are labeled with pairs of $G$'s edges to be compared, each of the two outgoing tree edges
+corresponds to one possible result of the comparison.\foot{There are two possible
+outcomes since there is no reason to compare an~edge with itself and we, as usually,
+expect that the edge weights are distinct.}
+Leaves of the tree are labeled with spanning trees of the graph~$G$.
+
+A~\df{computation} of the decision tree on a~specific permutation of edge weights
+in~$G$ is the path from the root to a~leaf such that the outcome of every comparison
+agrees with the edge weights. The result of the computation is the spanning tree
+assigned to its final leaf.
+A~decision tree is \df{correct} iff for every permutation the corresponding
+computation results in the real MSF of~$G$ with the particular weights.
+
+The \df{time complexity} of a~decision tree is defined as its depth. It therefore
+bounds the number of comparisons spent on every path. (It need not be equal since
+some paths need not correspond to an~actual computation --- the sequence of outcomes
+on the path could be unsatisfiable.)
+
+A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
+among the correct decision trees for the given graph.
+We will denote an~arbitrary optimal decision tree for~$G$ by~${\cal D}(G)$ and its
+complexity by~$D(G)$.
+
+The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~$D(G)$
+over all graphs~$G$ with $n$~vertices and~$m$ edges.
+
+\obs
+Decision trees are the most general deterministic comparison-based computation model possible.
+The only operations that count in its time complexity are comparisons. All
+other computation is free, including solving NP-complete problems or having
+access to an~unlimited source of non-uniform constants. The decision tree
+complexity is therefore an~obvious lower bound on the time complexity of the
+problem in all other comparison-based models.
+
+The downside is that we do not know any explicit construction of the optimal
+decision trees, or at least a~non-constructive proof of their complexity.
+On the other hand, the complexity of any existing comparison-based algorithm
+can be used as an~upper bound on the decision tree complexity. For example:
+
+\lemma
+$D(m,n) \le 4/3 \cdot n^2$.
+
+\proof
+Let us count the comparisons performed by the Contractive Bor\o{u}vka's algorithm
+(\ref{contbor}), tightening up the constants in its previous analysis in Theorem
+\ref{contborthm}. In the first iteration, each edge participates in two comparisons
+(one per endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$
+comparisons. Then the number of vertices drops at least by a~factor of two, so
+the subsequent iterations spend at most $(n/2)^2, (n/4)^2, \ldots$ comparisons, which sums
+to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$. Between the Bor\o{u}vka steps,
+we flatten the multigraph to a~simple graph, which also needs some comparisons,
+but for every such comparison we remove one of the participating edges, which saves
+at least one comparison in the subsequent steps.
+\qed
+
+\para
+Of course we can get sharper bounds from the better algorithms, but we will first
+show how to find the optimal trees using brute force. The complexity of the search
+will be of course enormous, but as we already promised, we will need the optimal
+trees only for very small subgraphs.
+
+\lemman{Construction of optimal decision trees}\id{odtconst}%
+An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
+the Pointer Machine in time $\O(2^{2^{4n^2}})$.
+
+\proof
+We will try all possible decision trees of depth at most $2n^2$
+(we know from the previous lemma that the desired optimal tree is shallower). We can obtain
+any such tree by taking the complete binary tree of exactly this depth
+and labeling its $2\cdot 2^{2n^2}-1$ vertices with comparisons and spanning trees. Those labeled
+with comparisons become internal vertices of the decision tree, the others
+become leaves and the parts of the tree below them are removed. There are less
+than $n^4$ possible comparisons and less than $2^{n^2}$ spanning trees of~$G$,
+so the number of candidate decision trees is bounded by
+$(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}}$.
+
+We will enumerate the trees in an~arbitrary order, test each of them for correctness and
+find the shallowest tree among those correct. Testing can be accomplished by running
+through all possible permutations of edges, each time calculating the MSF using any
+of the known algorithms and comparing it with the result given by the decision tree.
+The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
+and each one can be checked in time $\O(\poly(n))$.
+
+On the Pointer Machine, trees and permutations can be certainly enumerated in time
+$\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore
+$\O(2^{2^{3n^2}} \cdot 2^{n^3} \cdot \poly(n)) = \O(2^{2^{4n^2}})$.
+\qed
+
+\paran{Basic properties of decision trees}%
+The following properties will be useful for analysis of algorithms based
+on precomputed decision trees. We will omit some technical details, referring
+the reader to section 5.1 of the Pettie's article \cite{pettie:optimal}.
+
+\lemma\id{dtbasic}%
+The decision tree complexity $D(m,n)$ of the MSF satisfies:
+\numlist\ndotted
+\:$D(m,n) \ge m/2$ for $m,n > 2$.
+\:$D(m',n') \ge D(m,n)$ whenever $m'\ge m$ and $n'\ge n$.
+\endlist
+
+\proof
+For every $m,n>2$ there is a~graph on $n$~vertices and $m$~edges such that
+every edge lies on a~cycle. Every correct MSF decision tree for this graph
+has to compare each edge at least once. Otherwise the decision tree cannot
+distinguish between the case when an~edge has the lowest of all weights (and
+thus it is forced to belong to the MSF) and when it has the highest weight (so
+it is forced out of the MSF).
+
+Decision trees for graphs on $n'$~vertices can be used for graphs with $n$~vertices
+as well --- it suffices to add isolated vertices, which does not change the MSF.
+Similarly, we can increase $m$ to~$m'$ by adding edges parallel to an~existing
+edge and making them heavier than the rest of the graph, so that they can never
+belong to the MSF.
+\qed
+
+\defn
+Subgraphs $C_1,\ldots,C_k$ of a~graph~$G$ are called the \df{compartments} of~$G$
+iff they are edge-disjoint, their union is the whole graph~$G$ and
+$\msf(G) = \bigcup_i \msf(C_i)$ for every permutation of edge weights.
+
+\lemma\id{partiscomp}%
+The clusters $C_1,\ldots,C_k$ generated by the Partition procedure of the
+previous section (Algorithm \ref{partition}) are compartments of the graph
+$H=\bigcup_i C_i$.
+
+\proof
+The first and second condition of the definition of compartments follow
+from the Partitioning theorem (\ref{partthm}), so it remains to show that $\msf(H)$
+is the union of the MSF's of the individual compartments. By the Cycle rule
+(Lemma \ref{redlemma}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
+it is the heaviest edge on some cycle. It is therefore sufficient to prove that
+every cycle in~$H$ is contained within a~single~$C_i$.
+
+Let us consider a~cycle $K\subseteq H$ and a~cluster~$C_i$ such that it contains
+an~edge~$e$ of~$K$ and all clusters constructed later by the procedure do not contain
+any. If $K$~is not fully contained in~$C_i$, we can extend the edge~$e$ to a~maximal
+path contained in both~$K$ and~$C_i$. Since $C_i$ shares at most one vertex with the
+earlier clusters, there can be at most one edge from~$K$ adjacent to the maximal path,
+which is impossible.
+\qed
+
+\lemma
+Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then there exists an~optimal
+MSF decision tree for~$G$ that does not compare edges of distinct compartments.
+
+\proofsketch
+Consider a~subset~$\cal P$ of edge weight permutations~$w$ that satisfy $w(e) < w(f)$
+whenever $e\in C_i, f\in C_j, i<j$. For such permutations, no decision tree can
+gain any information on relations between edge weights in a~single compartment by
+inter-compartment comparisons --- the results of all such comparisons are determined
+in advance.
+
+Let us take an~arbitrary correct decision tree for~$G$ and restrict it to
+vertices reachable by computations on~$\cal P$. Whenever a~vertex contained
+an~inter-compartment comparison, it has lost one of its sons, so we can remove it
+by contracting its only outgoing edge. We observe that we get a~decision tree
+satisfying the desired condition and that this tree is correct.
+
+As for the correctness, the MSF of a~single~$C_i$ is uniquely determined by
+comparisons of its weights and the set~$\cal P$ contains all combinations
+of orderings of weights inside individual compartments. Therefore every
+spanning tree of every~$C_i$ and thus also of~$H$ is properly recognized.
+\qed
+
+\lemma\id{compartsum}%
+Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then $D(G) = \sum_i D(C_i)$.
+
+\proofsketch
+A~collection of decision trees for the individual compartments can be ``glued together''
+to a~decision tree for~$G$. We take the decision tree for~$C_1$, replace every its leaf
+by a~copy of the tree for~$C_2$ and so on. Every leaf~$\ell$ of the compound tree will be
+labeled with the union of labels of the original leaves encountered on the path from
+the root to~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$.
+
+The other inequality requires more effort. We use the previous lemma to transform
+the optimal decision tree for~$G$ to another of the same depth, but without inter-compartment
+comparisons. Then we prove by induction on~$k$ and then on the depth of the tree
+that this tree can be re-arranged, so that every computation first compares edges
+from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed
+to decision trees for the $C_i$'s. Also, without loss of efficiency all trees for
+a~single~$C_i$ can be made isomorphic to~${\cal D}(C_i)$.
+\qed
+
+\cor\id{dtpart}%
+If $C_1,\ldots,C_k$ are the clusters generated by the Partition procedure (Algorithm \ref{partition}),
+then $D(\bigcup_i C_i) = \sum_i D(C_i)$.
+
+\proof
+Lemma \ref{partiscomp} tells us that $C_1,\ldots,C_k$ are compartments of the graph
+$\bigcup C_i$, so we can apply Lemma \ref{compartsum} on them.
+\qed
+
+\cor\id{dttwice}%
+$2D(m,n) \le D(2m,2n)$ for every $m,n$.
+
+\proof
+For an~arbitrary graph~$G$ with $m$~edges and $n$~vertices, we create a~graph~$G_2$
+consisting of two copies of~$G$ sharing a~single vertex. The copies of~$G$ are obviously
+compartments of~$G_2$, so by Lemma \ref{compartsum} it holds that $D(G_2) = 2D(G)$.
+Taking a~maximum over all choices of~$G$ yields $D(2m,2n) \ge \max_G D(G_2) = 2D(m,n)$.
+\qed
+
+%--------------------------------------------------------------------------------
+
+\section{An optimal algorithm}\id{optalgsect}%
+
+Once we have developed the soft heaps, partitioning and MST decision trees,
+it is now simple to state the Pettie's and Ramachandran's MST algorithm
+and prove that it is asymptotically optimal among all MST algorithms in
+comparison-based models. Several standard MST algorithms from the previous
+chapters will also play their roles.
+
+We will describe the algorithm as a~recursive procedure. When the procedure is
+called on a~graph~$G$, it sets the parameter~$t$ to roughly $\log^{(3)} n$ and
+it calls the \<Partition> procedure to split the graph into a~collection of
+clusters of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision
+trees to find the MSF of the clusters. The graph obtained by contracting
+the clusters is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's
+algorithm runs on it in linear time. Afterwards we combine the MSF's of the clusters
+and of the contracted graphs, we mix in the corrupted edges and run two iterations
+of the Contractive Bor\o{u}vka's algorithm. This guarantees reduction in the number of
+both vertices and edges by a~constant factor, so we can efficiently recurse on the
+resulting graph.
+
+\algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
+\algo
+\algin A~connected graph~$G$ with an~edge comparison oracle.
+\:If $G$ has no edges, return an~empty tree.
+\:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}
+\:Call \<Partition> (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
+ a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges.
+\:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees.
+\:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph}
+\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
+\:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
+\:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
+ getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
+\:$F_C \= \mst(G_C)$ obtained by a~recursive call to this algorithm.
+\:Return $F_B \cup F_C$.
+\algout The minimum spanning tree of~$G$.
+\endalgo
+
+Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm})
+and from the proofs of the respective algorithms used as subroutines. Let us take a~look at
+the time complexity. We will be careful to use only the operations offered by the Pointer Machine.
+
+\lemma\id{optlemma}%
+The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence:
+$$
+T(m,n) \le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m,
+$$
+where~$c_1$ and~$c_2$ are some positive constants and $D$~is the decision tree complexity
+from the previous section.
+
+\proof
+The first two steps of the algorithm are trivial as we have linear time at our
+disposal.
+
+By the Partitioning theorem (\ref{partthm}), the call to \<Partition> with~$\varepsilon$
+set to a~constant takes $\O(m)$ time and it produces a~collection of clusters of size
+at most~$t$ and at most $m/4$ corrupted edges. It also guarantees that the
+connected components of the union of the $C_i$'s have at least~$t$ vertices
+(unless there is just a~single component).
+
+To apply the decision trees, we will use the framework of topological computations developed
+in Section \ref{bucketsort}. We pad all clusters in~$\C$ with isolated vertices, so that they
+have exactly~$t$ vertices. We use a~computation that labels the graph with a~pointer to
+its optimal decision tree. Then we apply Theorem \ref{topothm} combined with the
+brute-force construction of optimal decision trees from Lemma \ref{odtconst}. Together they guarantee
+that we can assign the decision trees to the clusters in time:
+$$\O\Bigl(\Vert\C\Vert + t^{t(t+2)} \cdot \bigl(2^{2^{4t^2}} + t^2\bigr)\Bigr)
+= \O\Bigl(m + 2^{2^{2^t}}\Bigr)
+= \O(m).$$
+Execution of the decision tree on each cluster~$C_i$ then takes $\O(D(C_i))$ steps.
+
+The contracted graph~$G_A$ has at most $n/t = \O(n / \log^{(3)}n)$ vertices and asymptotically
+the same number of edges as~$G$, so according to Corollary \ref{ijdens}, the Iterated Jarn\'\i{}k's
+algorithm runs on it in linear time.
+
+The combined graph~$G_B$ has~$n$ vertices, but less than~$n$ edges from the
+individual spanning trees and at most~$m/4$ additional edges which were
+corrupted. The Bor\o{u}vka steps on~$G_B$ take $\O(m)$
+time by Lemma \ref{boruvkaiter} and they produce a~graph~$G_C$ with at most~$n/4$
+vertices and at most $n/4 + m/4 \le m/2$ edges. (The $n$~tree edges in~$G_B$ are guaranteed
+to be reduced by the Bor\o{u}vka's algorithm.) It is easy to verify that this
+graph is still connected, so we can recurse on it.
+
+The remaining steps of the algorithm can be easily performed in linear time either directly
+or in case of the contractions by the bucket-sorting techniques of Section \ref{bucketsort}.
+\qed
+
+\paran{Optimality}%
+The properties of decision tree complexity, which we have proven in the previous
+section, will help us show that the time complexity recurrence is satisfied by a~constant
+multiple of the decision tree complexity $D(m,n)$ itself. This way, we will prove
+the following theorem:
+
+\thmn{Optimality of the Optimal algorithm}
+The time complexity of the Optimal MST algorithm \ref{optimal} is $\Theta(D(m,n))$.
+
+\proof
+We will prove by induction that $T(m,n) \le cD(m,n)$ for some $c>0$. The base
+case is trivial, for the induction step we will expand on the previous lemma:
+\def\eqalign#1{\null\,\vcenter{\openup\jot
+ \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
+ \crcr#1\crcr}}\,}
+$$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
+T(m,n)
+ &\le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m &(Lemma \ref{optlemma})\cr
+ &\le c_1 D({\textstyle\bigcup}_i C_i) + T(m/2, n/4) + c_2 m &(Corollary \ref{dtpart})\cr
+ &\le c_1 D(m,n) + T(m/2, n/4) + c_2m &(definition of $D(m,n)$)\cr
+ &\le c_1 D(m,n) + cD(m/2, n/4) + c_2m &(induction hypothesis)\cr
+ &\le c_1 D(m,n) + c/2\cdot D(m,n/2) + c_2m &(Corollary \ref{dttwice})\cr
+ &\le c_1 D(m,n) + c/2\cdot D(m,n) + 2c_2 D(m,n) &(Lemma \ref{dtbasic})\cr
+ &\le (c_1 + c/2 + 2c_2) \cdot D(m,n)&\cr
+ &\le cD(m,n). &(by setting $c=2c_1+4c_2$)\cr
+}}$$
+The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound on
+the time complexity of every comparison-based algorithm.
+\qed
+
+\paran{Complexity of MST}%
+As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem
+is still open and so therefore is the time complexity of the optimal algorithm. However,
+every time we come up with another comparison-based algorithm, we can use its complexity
+(or more specifically the number of comparisons it performs, which can be even lower)
+as an~upper bound on the optimal algorithm.
+
+The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$.\foot{$\alpha(m,n)$
+is a~certain inverse of the Ackermann's function, $\lambda_k(n)$ is the row inverse of the same
+function. See \ref{ackerinv} for the exact definitions.}
+It has been discovered by Chazelle \cite{chazelle:ackermann} as an~improvement of his previous
+$\O(m\timesalpha(m,n)\cdot\log\alpha(m,n))$ algorithm \cite{chazelle:almostacker}.
+It is also based on the ideas of this chapter --- in particular the soft heaps and robust contractions.
+The algorithm is very complex and it involves a~lot of elaborate
+technical details, so we only refer to the original paper here. Another algorithm of the same
+complexity, using similar ideas, has been discovered independently by Pettie \cite{pettie:ackermann}, who,
+having the optimal algorithm at hand, does not take care about the low-level details and he only
+bounds the number of comparisons. Using any of these results, we can prove an~Ackermannian
+upper bound on the optimal algorithm:
+
+\thmn{Upper bound on complexity of the Optimal algorithm}\id{optthm}%
+The time complexity of the Optimal MST algorithm is $\O(m\timesalpha(m,n))$.
+
+\proof
+We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Chazelle \cite{chazelle:ackermann}
+or Pettie \cite{pettie:ackermann}.
+\qed
+
+Similarly to the Iterated Jarn\'\i{}k's algorithm, this bound is actually linear for classes of graphs
+that do not have density extremely close to constant:
+
+\cor\id{lambdacor}%
+The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot \lambda_k(n)$ for any fixed~$k$.
+
+\proof
+Combine the previous theorem with Lemma \ref{alphaconst}.
+\qed
+
+\rem
+It is also known from \cite{pettie:optimal} that when we run the Optimal algorithm on a~random
+graph drawn from either $G_{n,p}$ (random graphs on~$n$ vertices, each edge is included with probability~$p$
+independently on the other edges) or $G_{n,m}$ (we draw the graph uniformly at random from the
+set of all graphs with~$n$ vertices and $m$~edges), it runs in linear time with high probability,
+regardless of the edge weights.
+
+\paran{Models of computation}%
+Another important consequence of the optimal algorithm is that when we aim for a~linear-time
+MST algorithm (or for proving that it does not exist), we do not need to care about computational
+models at all. The elaborate RAM data structures of Chapter \ref{ramchap}, which have helped us
+so much in the case of integer weights, cannot help if we are allowed to access the edge weights
+by performing comparisons only. We can even make use of non-uniform objects given by some sort
+of oracle. Indeed, whatever trick we employ to achieve linear time complexity, we can mimic it in the
+world of decision trees and thus we can use it to show that the algorithm we already knew is
+also linear.
+This however applies to deterministic algorithms only --- we have shown that access to a~source
+of random bits allows us to compute the MST in expected linear time (the KKT algorithm, \ref{kkt}).
+There were attempts to derandomize the KKT algorithm, but so far the best result in this direction
+is the randomized algorithm also by Pettie \cite{pettie:minirand} which achieves expected linear time
+complexity with only $\O(\log^* n)$ random bits.
\endpart
projects / saga.git / blobdiff