X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=opt.tex;h=067ac93a268cc556e548fbb371b596b71acba4d7;hb=124f193d14bed24539c5cd59407637cc38dbe740;hp=823f5ef06d058e80ab6233c9aa84787376fe3073;hpb=d7388c73212134c2fd9cce9370d27a7922c78c1b;p=saga.git diff --git a/opt.tex b/opt.tex index 823f5ef..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,62 +28,77 @@ 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$, -\:$\(P,Q)$ --- merge two heaps into one, more precisely insert all elements of a~heap~$Q$ - to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$), -\:$\(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 +\>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 (possibly corrupted) -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 correct values. +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$ -elements are greater than~$x$ and at least $n/3$ ones are smaller. Depending on the value -of~$k$, we can always throw away one of these parts and recurse on the rest (similarly to -the Hoare's Quickselect algorithm \cite{hoare:qselect}). The total time complexity will -be $\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$. We have obtained a~nice alternative to the standard -linear-time selection algorithm by Blum \cite{blum:selection}. The same trick can be used +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)$. + +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, the original C~code in the Chazelle's -paper uses this representation internally.} -Each vertex~$v$ of the tree remembers a~doubly-linked list $\(v)$ of values. The +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 former vertices will be called \df{white}, the latter +permanently occupied. The left sons will be called \df{white}, the right ones \df{black.} (See the picture.) -The first value in the list is called the \df{controlling key} of the vertex, +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 less than the \'s of its sons. +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 rank of leaves is always zero, the rank of every internal vertex must be strictly -greater than the ranks of its sons. We define the rank of a~queue to be equal to the -rank of its root vertex and similarly for its \. +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 @@ -82,48 +108,49 @@ ranks correspond to vertex heights. (black vertices contain items, numbers indicate ranks)}} \obs -A~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 a~complete queue of the same +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 one whose \ is smaller. +the son whose \ is smaller. -Sometimes, we will need to split a~queue to smaller queues. We will call this operation +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. -We will now combine the soft queues to the soft heap. - \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}, the last queue will be its \df{tail}; + 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; -\:and a~global parameter~$r\in{\bb N}$, to be set depending on~$\varepsilon$. +\: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 has length at least~$k/2$. +its leftmost path contains at least~$k/2$ vertices. + +\paran{Operations on soft heaps} -\para \em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble -the heap with the smaller maximum rank and we insert its queues to the other heap. +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, similarly to addition of binary numbers. -Finally we have to update the suffix minima by walking the new list backwards +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 @@ -131,9 +158,9 @@ a~single-element heap and melding it to the destination heap. \algn{Creating a~new soft heap} \algo -\algin A~parameter~$\varepsilon$. +\algin The~parameter~$\varepsilon$ (the accuracy of the heap). \:Allocate memory for a~new heap structure~$H$. -\:Initialize the list of queues in~$H$ as an~empty list. +\: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 @@ -141,26 +168,26 @@ a~single-element heap and melding it to the destination heap. \algn{Melding of two soft heaps} \algo \algin Two soft heaps~$P$ and~$Q$. -\:If the heap~$P$ has smaller rank than the heap~$Q$, exchange their item lists. +\: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 it contains -an~empty queue of infinite rank.} +\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 before~$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$. -\:::$p\=$ the successor of~$p$. +\:::$\\=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'\=$ successor of~$p$. +\::$p'\=\$ of the successor of~$p$. \::If $\(p) < \(p')$, set $\(p)\=p$. -\::Otherwise set $\(p)\=\(p')$. +\::Otherwise set $\(p)\=p'$. \:Destroy the heap~$Q$. \algout The merged heap~$P$. \endalgo @@ -168,14 +195,14 @@ an~empty queue of infinite rank.} \algn{Insertion of an~element to a~soft heap} \algo \algin A~heap~$H$ and a~new element~$x$. -\:Create a~new heap~$H'$ with the same parameters as~$H$. Let~$H'$ contain a~sole queue of rank~0, +\: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 -\para -So far, the mechanics of the soft heaps was almost identical to the binomial heaps +\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. @@ -187,41 +214,42 @@ represented by a~common \. This data-structural analogue of car pooling wi 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, as we must avoid corrupting +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 we allow. +the higher is the rank, the longer list will be allowed. \para -\em{Deleting of minimum} will follow this principle. The minimum is easy to locate +\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 -\ and we look inside the item list of the root of this queue. We remove the \em{last} -item from the list (we do not want the \ to change) and return it as the minimum. -(It is not necessarily the real minimum of all items, but always the minimum of those -uncorrupted.) +\. 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 tree. This can be best described recursively: We ask the left son to refill itself -(remember that the left son is always white, so there are no items to lose). If the new +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 the same time we keep +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%% -Ocassionally, 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 +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 its \ to $+\infty$), the current vertex is no longer -needed, as the items would just travel through it unmodified. We therefore want to -remove it. Instead of deleting it directly, we will rather make it point to its former -grandsons and we will remove the (now orhpaned) original son. This helps us to ensure -that both sons always have the same rank, which will be useful for the analysis. +(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 all refilling is done, we update the suffix minima by walking from the current +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 @@ -232,14 +260,15 @@ 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. -Let us translate these ideas to real (pseudo)code: +%%HACK%% +\>Let us translate these ideas to real (pseudo)code: -\algn{Deleting the minimum item of a~soft heap} +\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 last element~$x$ of the item list in the root of~$q$. -\:If the item list is empty: +\: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. @@ -248,7 +277,7 @@ Let us translate these ideas to real (pseudo)code: \:::Meld them back: $\(H,H')$. \::Otherwise: \:::Call \ on the root of~$q$. -\:::If $\(q)=+\infty$ (no items left), remove the tree~$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 @@ -258,7 +287,7 @@ Let us translate these ideas to real (pseudo)code: \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 sons of~$v$. +\:Let \ and~\ denote the respective sons of~$v$. \:Recurse: call $\(\)$. \:If $\(\) > \(\)$, swap the sons. \:Move the item list from \ to~$v$ (implying $\(v)=\(\)$). @@ -271,14 +300,20 @@ Let us translate these ideas to real (pseudo)code: \algout A~modified soft queue. \endalgo -\paran{Analysis of accuracy} -The description of the operations is complete, let us analyse their behavior +\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 in the history of the -structure by~$n$. We will also assume that the threshold~$r$ is even. +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 size of the item lists. +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 @@ -286,9 +321,9 @@ 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 ineqality trivially -holds. Let us continue by induction. Melds can affect it only in the favorable -direction (they sometimes move an~item list to a~vertex of a~higher rank) +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. @@ -298,8 +333,8 @@ 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 joined lists is at most $2^{\max(1,\lceil\(v)/2\rceil - 1 - r/2)}$, -so the result has at most $2^{\lceil\(v)/2\rceil - r/2}$ items. (The maximum +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 @@ -311,7 +346,7 @@ 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$ of them, because insertion adds one black vertex and +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. @@ -330,59 +365,67 @@ 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} \cdot \sum_{i=r+1}^k 2^{-i/2} +\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 formula is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ black vertices, -this makes less than $n_k/2^{k-2}$ corrupted items as we asserted. +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 analyse the amortized time complexity of the individual operations. -We will show that if we charge $\O(r)$ time against every element inserted, it suffices -to cover the cost of all other operations. We take a~look at the melds first. +\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 the smaller of their ranks plus -the time spent on carry propagation. The latter is easy to dispose of: since -every time there is a~carry, the total number of trees in all heaps decreases -by one, it suffices to charge $\O(1)$ against creation of a~tree. An~insert creates -one tree, dismantling creates at most $\(q)$ trees, all other operations -alter only the internal structure of trees. +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 +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 change for its rank~$k$ on all leaves +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 two heaps -of the same rank always produces a~heap of higher rank.) Hence at most~$n/2^k$ +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} = \O(n). +\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 the heap is never increased +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 -To estimate the time spent on deletions, we analyse the refills first. +Before we estimate the time spent on deletions, we analyse the refills. \lemma -Every call of the \ procedure spends time $\O(1)$ amortized. +Every invocation of \ takes time $\O(1)$ amortized. \proof When \ is called from the \ operation, it recurses on a~subtree of the @@ -391,7 +434,7 @@ and the upper part where list concatenation and thus also corruption takes place 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 pre-paid by the +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 @@ -401,7 +444,7 @@ when we visit a~vertex: \: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. So the +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 @@ -411,14 +454,14 @@ leaves and every internal vertex has outdegree two, so the total number of conca 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 small. It therefore cannot happen twice in a~row, -so it is clearly dominated by the other possibilities. +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 operations on the upper part is therefore $\O(n)$. +\>The total cost of all steps in the upper part is therefore $\O(n)$. \qed -It remains to examine the rest of the \ operation. +We now proceed with examining the \ operation. \lemma\id{shdelmin}% Every \ takes $\O(1)$ time amortized. @@ -427,12 +470,17 @@ Every \ takes $\O(1)$ time amortized. 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$. -The leftmost path is however always visited by the call to \, so we can -account the check on the refilling. The same holds for disassembling. We then have -to pay $\O(k)$ for melding the trees back to the heap, but since there are at most -$k/2$ trees, a~subtree of rank at least $k/2$ must have been deleted. This tree -contained at least $2^{k/2}$ vertices which are now permanently gone from the -data structure, so we can charge the cost of the meld against these vertices. +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, @@ -441,26 +489,702 @@ leftmost path and therefore it can be also paid for by \. (Incidentally, this was the only place where we needed the invariant.) \qed -Now we can put the bits together and laurel our effort with the following theorem: +\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}} +\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))$. At every moment, the heap contains at most -$\varepsilon n$ corrupted items. +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{shdelmin}, +\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 \, which yields the time bound. +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