X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=opt.tex;h=067ac93a268cc556e548fbb371b596b71acba4d7;hb=124f193d14bed24539c5cd59407637cc38dbe740;hp=7106858d077d8c4406cd93cb15aa62fbbf772314;hpb=a434094ac344dd846e680cafb7b775086659cea9;p=saga.git diff --git a/opt.tex b/opt.tex index 7106858..067ac93 100644 --- a/opt.tex +++ b/opt.tex @@ -2,14 +2,25 @@ \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 @@ -17,52 +28,1163 @@ Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly 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 -\:$\(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter, -\:$\(H,x)$ --- insert a~new element~$x$ to the heap~$H$, -\:$\(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), -\:$\(H)$ --- delete the minimum element of the heap~$H$ and return its value +\:$\(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$. +\:$\(H,x)$ --- Insert a~new item~$x$ into the heap~$H$. +\:$\(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$. +\:$\(H)$ --- Delete the minimum item of the heap~$H$ and return its value (optionally signalling that the value has been corrupted). +\:$\(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 $\(v)$ of values. The first value in the list -is called the \df{controlling key} of the vertex, denoted by $\(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 $\(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 $\(v)$. If the list is empty, we keep the most recently used +value or we set $\(v)=+\infty$. The \s obey the standard \df{heap order} +--- a~\ of a~parent is always smaller than the \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 \. + +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 \. To preserve the heap order, we will choose +the son whose \ 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 \ +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 $\(P) < \(Q)$, exchange the queue lists of~$P$ and~$Q$. +\:$p\=\(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\=\(Q)$. +\::If $\(p) < \(q)$, then $p\=$ the successor of~$p$, +\::else if $\(p) > \(q)$, remove~$q$ from~$Q$ and insert it to~$P$ before~$p$, +\::otherwise (the ranks are equal, we need to propagate the carry): +\:::$\\=p$. +\:::Remove~$p$ from~$P$ and set $p\=$ the original successor of~$p$. +\:::While $\(q)=\(\)$: +\::::Remove~$q$ from~$Q$. +\::::$\\=\(q, \)$. +\::::$q\=\(Q)$. +\:::Insert~\ before~$q$. +\:Update the suffix minima: Walk with~$p$ backwards to the head of~$P$: +\::$p'\=\$ of the successor of~$p$. +\::If $\(p) < \(p')$, set $\(p)\=p$. +\::Otherwise set $\(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. +\:$\(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 \ 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 \. 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 \, 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 \ of the head of the heap to the queue with the minimum +\. 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 \ 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 +\ 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 \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 \ 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 \ 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 \ of the head queue of~$H$ to locate the queue~$q$ with the smallest \. +\: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 $\(q)$ of them: +\:::Remove~$q$ from the list of queues. +\:::Recalculate the suffix minima as in the \ procedure. +\:::Dismantle~$q$ and create a~heap~$H'$ holding the resulting trees. +\:::Meld them back: $\(H,H')$. +\::Otherwise: +\:::Call \ on the root of~$q$. +\:::If $\(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 $\=+\infty$, + set $\(v)$ to~$+\infty$ and return. +\:Let \ and~\ denote the respective sons of~$v$. +\:Recurse: call $\(\)$. +\:If $\(\) > \(\)$, swap the sons. +\:Move the item list from \ to~$v$ (implying $\(v)=\(\)$). +\:If $\(v) > r$ and either $\(v)$ is odd or $\(v) > \(\)+1$, recurse once more: +\::Repeat steps 3--4. +\::Append the item list from \ to the item list at~$v$. +\:Clean up. If $\(\) = +\infty$: +\::If $\(\) = +\infty$, unlink and discard both sons. +\::Otherwise relink the sons of \ to~$v$ and discard \. +\algout A~modified soft queue. +\endalgo + +\para +\ 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 \. + +\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 \(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 \ procedure. + +Refilling sometimes just moves items upwards, which is safe, and sometimes it +joins two lists into one, which generally is not. When $\(v) \le r$, +no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either +$\(v)$ is odd or $\(w) < \(v)-1$ for any son~$w$ of~$v$ (remember +that both sons have the same rank). In both cases, $\lceil\(w)/2\rceil \le +\lceil\(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\(v)/2\rceil - 1 - r/2)}$, +so the new list has at most $2^{\lceil\(v)/2\rceil - r/2}$ items. (The maximum +has disappeared since $\(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(\(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 $\(q)$ +trees, and all other operations alter only the internal structure of trees. + +As for the $\O(\min(\(P),\(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 \ +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(\(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 \ takes time $\O(1)$ amortized. + +\proof +When \ is called from the \ 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 \ operation. + +\lemma\id{shdelmin}% +Every \ takes $\O(1)$ time amortized. + +\proof +Aside from refilling, which is $\O(1)$ by the previous lemma, the \ +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 \, 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 \), each vertex pays $\O(1)$. + +We must not forget that \ 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 \. (Incidentally, +this was the only place where we needed the invariant.) +\qed + +\s are easy not only to implement, but also to analyse: + +\lemma +Every \ takes $\O(1)$ time amortized. + +\proof +As all queues, vertices and items examined by \ 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 \, 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$~\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 \. 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 \ +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} +\::\ a~soft heap with accuracy~$\varepsilon$ and \ the edges adjacent to~$v_0$ into it. +\::While the heap is not empty and $\vert T\vert \le t$: +\:::\ 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.} +\::\ 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 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 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 \ (\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 \ 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