Decision trees started.

[saga.git] / opt.tex

\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Approaching Optimality}

\section{Soft heaps}

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))$ 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
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 lowered). This allows for
an~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
corrupted.

\defnn{Soft heap operations}%
The soft heap contains a~set of distinct items from a~totally ordered universe and it
supports the following operations:
\itemize\ibull
\:$\<Create>(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter~$\varepsilon$,
\:$\<Insert>(H,x)$ --- insert a~new item~$x$ to the heap~$H$,
\:$\<Meld>(P,Q)$ --- merge two heaps into one, more precisely move all items of a~heap~$Q$
  to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$),
\:$\<DeleteMin>(H)$ --- delete the minimum item of the heap~$H$ and return its value
  (optionally signalling that the value has been corrupted).
\:$\<Explode>(H)$ --- destroy the heap and return a~list of all items contained in it
  (again optionally marking those corrupted).
\endlist

\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.
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
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 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 \cite{chazelle:softheap} uses this representation internally.}
Each vertex~$v$ of the tree remembers a~doubly-linked list of items. The
item list in every left son will be used only temporarily and it will be kept
empty between operations. Only right sons and the root have their lists
permanently occupied. The left sons will be called \df{white}, the right ones
\df{black.} (See the picture.)

The first value in every list is called the \df{controlling key} of the vertex,
denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
value or we set $\<ckey>(v)=+\infty$. The \<ckey> obey the standard \df{heap order}
--- a~\<ckey> of a~parent is always smaller than the \<ckey>'s of its sons.

Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
The ranks of leaves are always zero, the rank of every internal vertex can be
arbitrary, but it must be strictly greater than the ranks of its sons. We
define the rank of the whole queue to be equal to the rank of its root vertex and
similarly for its \<ckey>.

A~queue is called \df{complete} if every two vertices joined by an~edge have rank
difference exactly one. In other words, it is a~complete binary tree and the
ranks correspond to vertex heights.

\figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\
(black vertices contain items, numbers indicate ranks)}}

\obs
The complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are
black (by induction). Any other queue can be trivially embedded to the complete queue of the same
rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex
ranks, colors and the ancestor relation.

The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
of the original roots and also its \<ckey>. To preserve the heap order, we will choose
the one whose \<ckey> is smaller.

Sometimes, we will also need to split a~queue to smaller queues. We will call this operation
\df{dismantling} the queue and it will happen only in cases when the item list in the root
is empty. It suffices to remove the leftmost (all white) path going from the root. From
a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing
if the original queue was not complete.

\figure{softheap2.eps}{\epsfxsize}{Joining and dismantling of soft queues}

We will now define the real soft heap and the operations on it.

\defn A~\df{soft heap} consists of:
\itemize\ibull
\:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks),
  we will call the first queue the \df{head} of the list, the last queue will be its \df{tail};
\:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \<ckey>
of those following it in the list;
\:a~global parameter~$r$: an~even integer to be set depending on~$\varepsilon$.
\endlist

\>We will define the \df{rank} of a~heap as the highest of the ranks of its queues
(that is, the rank of the heap's tail).

The heap always keeps the \df{Rank invariant:} When a~root of any tree has rank~$k$,
its leftmost path contains at least~$k/2$ vertices.

\paran{Operations on soft heaps}

\em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble
the heap of the smaller rank and we insert its queues to the other heap.
If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
a~single queue of rank~$k+1$ as already described and we propagate the new queue as
a~\df{carry} to the next iteration, similarly to addition of binary numbers.
Finally we have to update the suffix minima by walking the new list backwards
from the last inserted item.

\em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
a~single-element heap and melding it to the destination heap.

\algn{Creating a~new soft heap}
\algo
\algin The~parameter~$\varepsilon$ (the accuracy of the heap).
\:Allocate memory for a~new heap structure~$H$.
\:Initialize the list of queues in~$H$ to an~empty list.
\:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later).
\algout A~newly minted soft heap~$H$.
\endalgo

\algn{Melding of two soft heaps}
\algo
\algin Two soft heaps~$P$ and~$Q$.
\:If $\<rank>(P) < \<rank>(Q)$, exchange the item lists of~$P$ and~$Q$.
\:$p\=\<head>(P)$.
\brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that
there is an~empty queue of infinite rank there.}
\:While $Q$ still has some queues:
\::$q\=\<head>(Q)$.
\::If $\<rank>(p) < \<rank>(q)$, then $p\=$ the successor of~$p$,
\::else if $\<rank>(p) > \<rank>(q)$, remove~$q$ from~$Q$ and insert it to~$P$ before~$p$,
\::otherwise (the ranks are equal, we need to propagate the carry):
\:::$\<carry>\=p$.
\:::Remove~$p$ from~$P$ and set $p\=$ the original successor of~$p$.
\:::While $\<rank>(q)=\<rank>(\<carry>)$:
\::::Remove~$q$ from~$Q$.
\::::$\<carry>\=\<join>(q, \<carry>)$.
\::::$q\=\<head>(Q)$.
\:::Insert~\<carry> before~$q$.
\:Update the suffix minima: Walk with~$p$ backwards to the head of~$P$:
\::$p'\=\<suffix\_min>$ of the successor of~$p$.
\::If $\<ckey>(p) < \<ckey>(p')$, set $\<suffix\_min>(p)\=p$.
\::Otherwise set $\<suffix\_min>(p)\=p'$.
\:Destroy the heap~$Q$.
\algout The merged heap~$P$.
\endalgo

\algn{Insertion of an~element to a~soft heap}
\algo
\algin A~heap~$H$ and a~new element~$x$.
\:Create a~new heap~$H'$ of the same parameters as~$H$. Let~$H'$ contain a~sole queue of rank~0,
  whose only vertex has the element~$x$ in its item list.
\:$\<Meld>(H,H')$.
\algout An~updated heap~$H$.
\endalgo

\para
So far, the mechanics of the soft heaps were almost identical to the binomial heaps
and the reader could rightfully yawn. The things are going to get interesting
now as we approach the parts where corruption of items takes place.

If all item lists contain at most one item equal to the \<ckey> of the particular
vertex, no information is lost and the heap order guarantees that the minimum item
of every queue stays in its root. We can however allow longer lists and let the items
stored in a~single list travel together between the vertices of the tree, still
represented by a~common \<ckey>. This data-structural analogue of car pooling will
allow the items to travel at a~faster rate, but as only a~single item can be equal
to the \<ckey>, all other items will be inevitably corrupted.

We of course have to be careful about the size of the lists, because we must avoid corrupting
too many items. We will control the growth according to the vertex ranks. Vertices
with rank at most~$r$ will always contain just a~single item. Above this level,
the higher is the rank, the longer list will be allowed.

\para
\em{Deletion of minimum} will be based on this principle. The minimum is easy to locate
--- we follow the \<suffix\_min> of the head of the heap to the queue with the minimum
\<ckey>. There we look inside the item list of the root of the queue. We remove the \em{last}
item from the list (we do not want the \<ckey> to change) and we return it as the minimum.
(It is not necessarily the real minimum of all items, but always the minimum of their
possibly corrupted values.)

If the list becomes empty, we \em{refill} it with items from the lower levels of the
same queue. This process can be best described recursively: We ask the left son to refill itself
(remember that the left son is always white, so there are currently no items there). If the new
\<ckey> of the left son is smaller than of the right son, we immediately move the left
son's list to its parent. Otherwise, we exchange the sons and move the list from the
new left son to the parent. This way we obey the heap order and at the same time we keep
the white left son free of items.

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 \<ckey>'s). This
makes the lists grow longer and we want to do that roughly on every other level of the
tree. The exact condition will be that either the rank of the current vertex is odd,
or the difference in ranks between this vertex and its right son is at least two.

If refilling of the left son fails because there are no more items in that subtree
(we report this by setting its \<ckey> to $+\infty$), the current vertex is no longer
needed --- the items would just pass through it unmodified. We therefore want to
remove it. Instead of deleting it directly, we rather make it point to its former
grandsons and we remove the (now orhpaned) 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
queue to the head of the heap exactly as we did in the \<Meld> procedure.

Our only remaining worry is that the Rank invariant can be broken after the
refilling. When the leftmost path of the tree becomes too short, we just
\em{dismantle} the tree as already described and we meld the new trees back to
the heap. This is easier to handle when the item list at the root vertex is
empty. We will therefore move this check before the refilling of the root list.
It will turn out that we have enough time to always walk the leftmost path
completely, so no explicit counters are needed.

Let us translate these ideas to real (pseudo)code:

\algn{Deleting the minimum item from a~soft heap}
\algo
\algin A~soft heap~$H$.
\:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
\:Remove the final element~$x$ of the item list in the root of~$q$.
\:If the item list is empty:
\::Count the vertices on the leftmost path of~$q$.
\::If there are less than $\<rank>(q)$ of them:
\:::Remove~$q$ from the list of queues.
\:::Recalculate the suffix minima as in the \<Meld> procedure.
\:::Dismantle~$q$ and create a~heap~$H'$ holding the resulting trees.
\:::Meld them back: $\<Meld>(H,H')$.
\::Otherwise:
\:::Call \<Refill> on the root of~$q$.
\:::If $\<ckey>(q)=+\infty$ (no items left), remove the tree~$q$ from~$H$.
\:::Recalculate the suffix minima.
\algout The deleted minimum item~$x$ (possibly corrupted).
\endalgo

\algn{Refilling the item list of a~vertex}
\algo
\algin A~soft queue and its vertex~$v$ with an~empty item list.
\:Handle trivial cases: If~$v$ has no children or both have $\<ckey>=+\infty$,
  set $\<ckey>(v)$ to~$+\infty$ and return.
\:Let \<left> and~\<right> denote the respective sons of~$v$.
\:Recurse: call $\<Refill>(\<left>)$.
\:If $\<ckey>(\<left>) > \<ckey>(\<right>)$, swap the sons.
\:Move the item list from \<left> to~$v$ (implying $\<ckey>(v)=\<ckey>(\<left>)$).
\:If $\<rank>(v) > r$ and either $\<rank>(v)$ is odd or $\<rank>(v) > \<rank>(\<right>)+1$, recurse once more:
\::Repeat steps 3--4.
\::Append the item list from \<left> to the item list at~$v$.
\:Clean up. If $\<ckey>(\<right>) = +\infty$:
\::If $\<ckey>(\<left>) = +\infty$, unlink and discard both sons.
\::Otherwise relink the sons of \<left> to~$v$ and discard \<left>.
\algout A~modified soft queue.
\endalgo

\para
\<Explode> is trivial once we know how to recognize the corrupted items. It simply examines
all queues in the heap, walks the trees and the item lists of all vertices. It records
all items seen, the corrupted ones are those that different from their \<ckey>.

\paran{Analysis of accuracy}
The description of the operations is now complete, so let us analyse their behavior
and verify that we have delivered what we promised --- first the accuracy of
the structure, then the time complexity of operations. In the whole analysis,
we will denote the total number of elements inserted during the history of the
structure by~$n$. We will also frequently take advantage of knowing that the
threshold~$r$ is even.

We start by bounding the sizes of the item lists.

\lemma
For every vertex~$v$ of a~soft queue, the size $\ell(v)$ of its item list
satisfies:
$$\ell(v) \le \max(1, 2^{\lceil \<rank>(v)/2 \rceil - r/2}).$$

\proof
Initially, all item lists contain at most one item, so the ineqality trivially
holds. Let us continue by induction. Melds can affect it only in the favorable
direction (they ocassionally move an~item list to a~vertex of a~higher rank)
and so do deletes (they only remove items from lists). The only potentially
dangerous place is the \<Refill> procedure.

Refilling sometimes just moves items upwards, which is safe, and sometimes it
joins two lists into one, which generally is not. When $\<rank>(v) \le r$,
no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either
$\<rank>(v)$ is odd or $\<rank>(w) < \<rank>(v)-1$ for any son~$w$ of~$v$ (remember
that both sons have the same rank). In both cases, $\lceil\<rank>(w)/2\rceil \le
\lceil\<rank>(v)/2\rceil - 1$. By the induction hypothesis, the size of each
of the two joined lists is at most $2^{\max(1,\lceil\<rank>(v)/2\rceil - 1 - r/2)}$,
so the new list has at most $2^{\lceil\<rank>(v)/2\rceil - r/2}$ items. (The maximum
has disappeared since $\<rank>(v)>r$ and therefore the desired bound is at least~2.)
\qed

We will now sum the sizes of the lists over all vertices containing corrupted items.

\lemma\id{shcorrlemma}%
At any given time, the heap contains at most~$n/2^{r-2}$ corrupted items.

\proof
We first prove an~auxiliary claim: The master trees of all queues contain at most~$n$
black vertices. This follows by induction: If no deletions have taken place,
there are exactly~$n$ black vertices, because insertion adds one black vertex and
melding preserves their number. A~deletion affects the master trees only when
dismantling takes place and then it only removes a~black vertex.

An~obvious upper bound on the number of corrupted items is the total size of item
lists in all vertices of rank greater than~$r$. We already know from the previous
lemma that the list sizes are limited by a~function of the ranks. A~complete tree
is obviously the worst case, so we will prove that this lemma holds for the master
tree of every queue in the heap. The actual trees can be much sparser, but the
above claim guarantees that the total size of the master trees is bounded by the
number of insertions properly.

So let us consider a~complete tree of~rank~$k$. It has exactly $2^{k-i}$ vertices
of rank~$i$ and each such vertex contains a~list of at most~$2^{\lceil i/2\rceil - r/2}$
items by the previous lemma. Summing over all ranks greater than~$r$, we get that
the total number of corrupted items in this tree is at most:
$$
\sum_{i=r+1}^k 2^{k-i}\cdot 2^{\lceil i/2\rceil - r/2}
= 2^{k-r/2} \cdot \sum_{i=r+1}^k 2^{\lceil i/2\rceil - i}
\le 2^{k-r/2+1/2} \cdot \sum_{i=r+1}^k 2^{-i/2}
\le 2^{k-r} \cdot \sum_{i=0}^\infty 2^{-i/2}.
$$
The sum of a~geometric series with quotient $2^{-1/2}$ is less than four, so the
last expression is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ black vertices,
this makes less than $n_k/2^{r-2}$ corrupted items as we asserted.
\qed

\paran{Analysis of time complexity}
Now we will examine the amortized time complexity of the individual operations.
We will show that if we charge $\O(r)$ time against every element inserted, it is enough
to cover the cost of all other operations.

All heap operations use only pointer operations, so it will be easy to derive the time
bound in the Pointer machine model. The notable exception is however that the procedures
often refer to the ranks, which are integers on the order of $\log n$, so they cannot
fit in a~single memory cell. For the time being, we will assume that the ranks can
be manipulated in constant time, postponing the proof for later.

We take a~look at the melds first.

\lemma\id{shmeld}%
The amortized cost of a~meld is $\O(1)$, except for melds induced by dismantling
which take $\O(\<rank>(q))$, where $q$~is the queue to be dismantled.

\proof
The real cost of a~meld of heaps $P$ and~$Q$ is linear in the smaller of
their ranks, plus the time spent on carry propagation. The latter is easy to
dispose of: Every time there is a~carry, the total number of trees in all
heaps decreases by one. So it suffices to charge $\O(1)$ against creation of
a~tree. An~insert creates one tree, dismantling creates at most $\<rank>(q)$
trees, and all other operations alter only the internal structure of trees.

As for the $\O(\min(\<rank>(P),\<rank>(Q)))$ part, let us assume for a~while that
no dismantling ever takes place and consider the \df{meld forest.} It is a~forest
whose leaves correspond to the $n$~single-element heaps constructed by \<Insert>
and each internal vertex represents a~heap arisen from melding its sons. The left
son will be the one with the greater or equal rank. We therefore want to bound
the sum of ranks of all right sons.

For every right son, we will distribute the change 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~strictly greater rank.) Hence at most~$n/2^k$
right sons have rank~$k$ and the total time charged against the leaves is bounded by:
$$
\sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n.
$$

Let us return dismantling to the game. When a~queue is dismantled, melding the parts
back to the heap takes $\O(\<rank>(q))$ time. We can therefore let the dismantling pay for it
and omit such induced melds from the meld forest. As the rank of a~heap is never increased
by induced melds, the above calculation is still a~proper upper bound on the cost
of the regular melds.
\qed

Before we estimate the time spent on deletions, we analyse the refills.

\lemma
Every invokation of the \<Refill> procedure takes time $\O(1)$ amortized.

\proof
When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the
queue. This subtree can be split to the ``lossless'' lower part (rank~$r$ and below)
and the upper part where list concatenation and thus also corruption takes place. Whenever
we visit the lower part during the recursion, we spend at worst $\O(r)$ time there.
We will prove that the total time spent in the upper parts during the whole life of the
data structure is $\O(n)$. Since each upper vertex can perform at most two calls to the lower
part, the total time spent in the lower parts is $\O(rn)$. All this can be prepaid by the
inserts.

Let us focus on the upper part. There are three possibilities of what can happen
when we visit a~vertex:

\itemize\ibull

\:We delete it: Every vertex deleted has to have been created at some time in the past.
New vertices are created only during inserts and melds (when joining two trees) and
we have already shown that these operations have constant amortized complexity. Then the
same must hold for deletions.

\:We recurse twice and concatenate the lists: The lists are disassembled only when
they reach the root of the tree, otherwise they are only concatenated. We can easily
model the situation by a~binary tree forest similar to the meld forest. There are~$n$
leaves and every internal vertex has outdegree two, so the total number of concatenations
is at most~$n$. Each of them can be performed in constant time as the list is doubly linked.

\:We recurse only once: This occurs only if the rank is even and the gap between the
rank of this vertex and its sons is equal to~1. It therefore cannot happen twice in a~row,
thus it is clearly dominated by the cost of the other possibilities.

\endlist
\>The total cost of all steps in the upper part is therefore $\O(n)$.
\qed

We now proceed with examining the \<DeleteMin> operation.

\lemma\id{shdelmin}%
Every \<DeleteMin> takes $\O(1)$ time amortized.

\proof
Aside from refilling, which is $\O(1)$ by the previous lemma, the \<DeleteMin>
takes care of the Rank invariant. This happens by checking the length of the leftmost
path and dismantling the tree if the length is too far from the tree's rank~$k$.
When the invariant is satisfied, the leftmost path is visited by the subsequent
call to \<Refill>, so we can account the check on the refilling.

When we are dismantling, we have to pay $\O(k)$ for the operation itself and
another $\O(k)$ for melding the trees back to the heap. Since we have produced at most
$k/2$ subtrees of distinct ranks, some subtree of rank $k/2$ or more must be missing.
Its master tree contained at least $2^{k/2}$ vertices which are now permanently gone
from the data structure, so we can charge the cost against them.
A~single vertex can participate in the master trees of several dismantlings, but their
ranks are always strictly increasing. By the same argument as in the proof of
Lemma \ref{shmeld} (complexity of \<Meld>), each vertex pays $\O(1)$.

We must not forget that \<DeleteMin> also has to recalculate the suffix minima.
In the worst case, it requires touching $k$~trees. Because of the Rank invariant,
this is linear in the size of the
leftmost path and therefore it can be also paid for by \<Refill>. (Incidentally,
this was the only place where we needed the invariant.)
\qed

\<Explode>s are easy not only to implement, but also to analyse:

\lemma
Every \<Explode> takes $\O(1)$ time amortized.

\proof
As all queues, vertices and items examined by \<Explode> are forever gone from the heap,
we can charge the constant time spent on each of them against the operations
that have created them.
\qed

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 create a~``yardstick'' --- a~double 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 as necessary.

Comparison of two ranks for equality is then trivial, as is incrementing or decrementing
the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even
flag in every tick. This covers all uses of ranks except for the comparisons for inequality
when melding. In step~1 of \<Meld>, we just mark the ticks of the two ranks and walk
the yardstick from the beginning until we come across a~mark. Thus we compare the ranks
in time proportional to the smaller of them, which is the real cost of the meld anyway.
The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put
to~$P$ are strictly increasing, we can start walking the list at the rank of the previous
element in~$P$. The cost is then the difference between the current and the previous rank
and their sum telescopes, again to the real cost of the meld.
\qed

Now we can put the bits together and laurel our effort with the following theorem:

\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
in time $\O(n\log(1/\varepsilon))$ on the Pointer machine. At every moment, the
heap contains at most $\varepsilon n$ corrupted items.

\proof
We set the parameter~$r$ to~$2+2\lceil\log (1/\varepsilon)\rceil$. The rest follows
from the analysis above. By Lemma \ref{shcorrlemma}, there are always at most $n/2^{r-2}
\le \varepsilon n$ corrupted items in the heap. By Lemma \ref{shmeld}--\ref{shyards},
the time spent on all operations in the sequence can be paid for by charging $\O(r)$ time
against each \<Insert>. This yields the time bound.
\qed

\rem
When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any
items, so it can be used like any usual 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 occured, 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~usual 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
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 original
version without active edges (\ref{jarnik}) as the soft heap lacks the \<Decrease>
operation. This honest, 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 a~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 will 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,
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$ ($u,x\in C$ and $v,y\not\in C$),
they enter the algorithm's heap at some time. Without loss of generality $uv$~is the first.
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 and 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)$. We know that the edges which
does not participate in the MSF are exactly those which are the heaviest on some cycle
(this is the Cycle rule \ref{cyclerule}).

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 contracted the subgraph~$C$, the cycle is present
in~$G$, too. Otherwise we consider the edges $e,f$ adjacent to~$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 ready to bring corruption back to the game now 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 edge weights in this
graph are pairwise distinct. While this is technically not true for the corruption
caused by soft heaps, we can easily make the weights unique.

If~$C$ is a~subgraph of~$G$, we will refer to the edges of~$R$ whose exactly
one endpoint lies in~$C$ by~$R^C$ (i.e., $R^C = R\cap \delta(C)$).

\lemman{Robust contraction}\id{robcont}%
Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
for some set of edges~$R$. 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 which do not belong to the right-hand side and 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 $e$~is the heaviest.
When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are finished.
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~$(G\crpt R)\cup 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
Our plan still is to mimic the Iterative Jarn\'\i{}k's algorithm. We will grow a~collection~$\C$
of non-overlapping contractible subgraphs and put aside the edges which got corrupted in the process.
We recursively compute the MSF of the 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 final MSF, but a~sparser graph containing it, on which we can continue.

We can formulate the exact partitioning algorithm as follows:

\algn{Partition a~graph to a~collection of contractible subgraphs}\id{partition}%
\algo
\algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the subgraphs,
  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 we currently grow}
\::$K=\emptyset$. \cmt{edges known to be corrupted}
\::\<Create> a~soft heap with accuracy~$\varepsilon$ and \<Insert> the edges adjacent to~$v_0$ in it.
\::While the heap is not empty and $\vert T\vert \le t$:
\:::\<DeleteMin> an~edge $uv$ from the heap, assume $u\in T$.
\:::If $uv$ was corrupted, add it to~$K$.
\:::If $v\in T$, drop the edge and repeat the previous two steps.
\:::$T\=T\cup\{v\}$.
\:::If $v$ is dead, break out of the current loop.
\:::Insert all edges incident with~$v$ to the heap.
\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the subgraph induced by the tree.}
\::\<Explode> the heap and add all remaining corrupted edges to~$K$.
\::$R^\C\=R^\C \cup \{ K^T \}$. \cmt{Record the ``interesting'' corrupted edges.}
\::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.}
\::Mark all vertices of~$T$ as ``dead''.
\algout The collection $\C$ of contractible subgraphs and the set~$R^\C$ of
corrupted edges in the neighborhood of these subgraphs.
\endalgo

\thmn{Partitioning to contractible subgraphs, Pettie \cite{pettie:optimal}}\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 subgraphs and a~set~$R^\C$ of corrupted edges such that:

\numlist\ndotted
\:All the $C_i$'s and the set~$R^\C$ are edge-disjoint.
\:Each $C_i$ contains at most~$t$ vertices.
\:Each vertex of~$G$ is contained in at least one~$C_i$.
\:The connected components of the union of all $C_i$'s 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
The algorithm grows a~series of trees. 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. Edges of~$R^\C$ are immediately deleted from the graph, so they never participate
in any tree. The algorithm stops only if all vertices are dead, so each vertex must have
entered some tree. Each $C_i$ is induced by some tree and the trees have at most~$t$ vertices
each, which limits the size of the $C_i$'s as well. This proves claims 1--3.

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 already
has~$t$ vertices, or it joins one of the existing trees (which 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~$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
in every direction, 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 subgraph~$C_i$ in the $i$-th phase (iteration of the outer
loop) 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 subgraph~$C_j$ by running the partial Jarn\'\i{}k's algorithm on the graph
$G_i = G\setminus\bigcup_{j<i} K_{\smash j}^{\C_j}$.
If it were not for corruption, the subgraph~$C_i$ would be contractible, as we already know from Example \ref{jarniscont}.
When the edges in~$K_i$ get corrupted, the subgraph is contractible in some corrupted graph
$G_i \crpt K_i$. (We have to be careful as the edges are becoming corrupted gradually,
but it is easy to check that it can only improve the situation.) Since $C_i$~is edge-disjoint
with the previous trees, it is also a~contractible subgraph of $(G_i / \bigcup_{j<i} C_j) \crpt K_i$.
Now we can use the Robust contraction lemma to show that:
$$
\msf\biggl(\bigl(G / \bigcup_{i<j} \bigr) \setminus \bigcup_{i<j} K_j^{\C_j} \biggr) \subseteq
\msf(C_i) \cup \msf\biggl(\bigl(G / \bigcup_{i\le j} \bigr) \setminus \bigcup_{i\le j} K_j^{\C_j} \biggr) \cup K_i^{C_i},
$$
which completes the induction step.
\qed

\lemman{Efficiency of Partition, Claim 7 of Theorem \ref{partthm}}
The Partition algorithm runs in time $\O(n+m\log(1/\varepsilon))$.

\proof
The inner loop (steps 7--13) processes the edges of the current subgraph~$C_i$ and also
the edges in its neighborhood $\delta(C_i)$. Steps 6 and~13 insert each such edge to the heap
at most once, so steps 8--12 also visit each edge at most once. For every edge, we spend
$\O(\log(1/\varepsilon))$ time amortized on inserting it and $\O(1)$ on the other operations
(by Theorem \ref{softheap} on performance of the soft heaps).

Each edge of~$G$ can participate in some $C_i\cup \delta(C_i)$ only twice before both its
ends die. The inner loop therefore processes $\O(m)$ edges total, so we spend $\O(m\log(1/\varepsilon))$
time there. The rest of the algorithm spends $\O(m)$ time on the other operations with subgraphs
and $\O(n)$ on identifying the live vertices.
\qed

%--------------------------------------------------------------------------------

\section{Decision trees}

The Pettie's algorithm combines the idea of robust partitioning with optimal decision
trees constructed by brute force for very small subgraphs. In this section, we will
explain the basics of the decision trees and prove several lemmata which will
turn out to be useful for the analysis of time complexity of the whole algorithm.

Let us consider all computations of a~comparison-based MST algorithm when we
run it on a~fixed graph~$G$ with all possible permutations of edge weights.
They can be described by a~tree. The root of the tree corresponds to the first
comparison performed by the algorithm and depending to its result, the computation
continues either in the left subtree or in the right subtree. There it encounters
another comparison and so on, until it arrives to a~leaf of the tree where the
spanning tree found by the algorithm is recorded.

Formally, the decision trees are defined as follows:

\defnn{Decision trees and their complexity}\id{decdef}%
A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
are labeled with pairs of edges to be compared, each of the two outgoing edges
corresponds to one possible result of the comparison.\foot{There is no reason
to compare two identical edges.}
Leaves of the tree are labeled with spanning trees of the graph~$G$.

A~\df{computation} of the decision tree on a~specific permutation of edge weights
in~$G$ is a~path from the root to a~leaf such that the outcome of every comparison
agrees with the edge weights. The result of the computation is the spanning tree
assigned to its final leaf.
A~decision tree is \df{correct} iff for every permutation the corresponding
computation results in the real MSF of~$G$ with the particular weights.

The \df{time complexity} of a~decision tree is defined as its depth. It therefore
bounds the number of comparisons spent on every path. (It need not be equal since
some paths need not correspond to an~actual computation --- the sequence of outcomes
on the path can be unsatifisfiable.)

A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
among the correct decision trees for the given graph.
We will denote an~arbitrary optimal decision tree for~$G$ by~${\cal D}(G)$ and its
complexity by~$D(G)$.

The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~$D(G)$
over all graphs~$G$ with $n$~vertices and~$m$ edges.

\obs
Decision trees are the most general comparison-based computation model possible.
The only operations which count in the time complexity are the comparisons. All
other computation is free, including solving NP-complete problems or having
access to an~unlimited source of non-uniform constants. The decision tree
complexity is therefore an~obvious lower bound on the time complexity of the
problem in all other models.

The downside is that we do not know any explicit construction of the optimal
decision trees, or at least a~non-constructive proof of their complexity.
On the other hand, the complexity of any existing comparison-based algorithm
can be used as an~upper bound for the decision tree complexity. For example:

\lemma
$D(m,n) \le 4/3 \cdot n^2$.

\proof
Let us count the comparisons performed by the contractive Bor\o{u}vka's algorithm.
(\ref{contbor}), tightening up the constants in the original analysis in Theorem
\ref{contborthm}. In the first phase, each edge participates in two comparisons
(one for each its endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$
comparisons. Then the number of vertices drops at least by a~factor of two, so
the subsequent phases spend $(n/2)^2, (n/4)^2, \ldots$ comparisons, which sums
to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$.
\qed

\para
Of course we can get sharper bounds from the better algorithms, but we will first
show how to find the optimal trees using brute force. The complexity of the search
will be of course enormous, but as we already promised, we will need the optimal
trees only for very small subgraphs.

\lemma
Optimal MST decision trees for all graphs on at most~$k$ vertices can be
constructed on the Pointer machine in time $\O(2^{2^{k^3}})$.

\proof
There are $2^{k\choose 2} \le 2^{k^2}$ undirected graphs on~$k$ vertices. Any
graph on less than~$k$ vertices can be expanded to $k$~vertices by adding isolated
vertices, which obviously do not affect the optimal decision tree.

For every graph, we will try all possible trees of depth at most $4/3\cdot k^2$
(we know from the previous lemma that the optimal tree is not deeper). Each such
tree has at most $2^{2k^2}$ internal vertices and at most $2^{2k^2}$ leaves.
All internal vertices are labeled with comparisons and there are less than $k^4$
ways how to select the edges to be compared. Each leaf is labeled with one of the
at most $2^{k^2}$ spanning trees. There are therefore at most $(2^{2k^2})^{2^{2k^2}}
\le 2^{2k^2\cdot 2^{2k^2}} \le 2^{2^{k^3}}$ candidate trees and we will enumerate them
in order of increasing depth.

\FIXME{Continue with verifying correctness.}

\qed




%--------------------------------------------------------------------------------

\section{An optimal algorithm}




\endpart