\section{Soft heaps}
+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 useless edges. A~notable exception is the randomized
+algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses
+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))$ on the Pointer machine. 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
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
+\:$\<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
+\:$\<Explode>(H)$ --- Destroy the heap and return a~list of all items contained in it
(again optionally marking those corrupted).
\endlist
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
+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.
\lemma\id{shyards}%
Every manipulation with ranks performed by the soft heap operations can be
-implemented on the Pointer machine in constant amortized time.
+implemented on the Pointer Machine in constant amortized time.
\proof
-We create a~``yardstick'' --- a~double linked list whose elements represent the possible
+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 as necessary.
\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
+in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
heap contains at most $\varepsilon n$ corrupted items.
\proof
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, \ref{cyclerule}).
+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
\para
We still intend to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
-of non-overlapping contractible subgraphs and put aside all edges that got corrupted in the process.
+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 that 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.
We can formulate the exact partitioning algorithm and its properties as follows:
-\algn{Partition a~graph to a~collection of contractible subgraphs}\id{partition}%
+\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 subgraphs,
+\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.}
\:::$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.}
+\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the cluster induced by the tree.}
\::\<Explode> the heap and add all remaining corrupted edges to~$K$.
\::$R^\C\=R^\C \cup K^T$. \cmt{Record the ``interesting'' corrupted edges.}
\::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.}
\::Mark all vertices of~$T$ as ``dead''.
-\algout The collection $\C$ of contractible subgraphs and the set~$R^\C$ of
-corrupted edges in the neighborhood of these subgraphs.
+\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 subgraphs, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
+\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 subgraphs and a~set~$R^\C$ of edges such that:
+$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of 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$.
+\: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 subgraphs~$C_i$ in~$G$.
+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
\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 of the algorithm,
+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 subgraph~$C_i$ by running the partial Jarn\'\i{}k's algorithm on the graph
+In the $i$-th phase we construct the cluster~$C_i$ by running the partial Jarn\'\i{}k's algorithm on the graph
$G_i = G\setminus\bigcup_{j<i} K_{\smash j}^{C_j}$.
-If it were not for corruption, the 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
+If it were not for corruption, the cluster~$C_i$ would be contractible, as we already know from Example \ref{jarniscont}.
+When the edges in~$K_i$ get corrupted, the cluster is contractible in some corrupted graph
$G_i \crpt K_i$. (We have to be careful as the edges are becoming corrupted gradually,
but it is easy to check that it can only improve the situation.) Since $C_i$~shares no edges
with~$C_j$ for any~$j<i$, we know that~$C_i$ also a~contractible subgraph of $(G_i / \bigcup_{j<i} C_j) \crpt K_i$.
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 inner loop (steps 7--13) processes the edges of the current cluster~$C_i$ and also
the edges in its neighborhood $\delta(C_i)$. Steps 6 and~13 insert every such edge to the heap
at most once, so steps 8--12 visit each edge also at most once. For every edge, we spend
$\O(\log(1/\varepsilon))$ time amortized on inserting it and $\O(1)$ on the other operations
Each edge of~$G$ can participate in some $C_i\cup \delta(C_i)$ only twice before both its
endpoints die. The inner loop therefore processes $\O(m)$ edges total, so it takes $\O(m\log(1/\varepsilon))$
-time. The remaining parts of the algorithm spend $\O(m)$ time on operations with subgraphs and corrupted edges
+time. The remaining parts of the algorithm spend $\O(m)$ time on operations with clusters and corrupted edges
and additionally $\O(n)$ on identifying the live vertices.
\qed
The \df{time complexity} of a~decision tree is defined as its depth. It therefore
bounds the number of comparisons spent on every path. (It need not be equal since
some paths need not correspond to an~actual computation --- the sequence of outcomes
-on the path could be unsatifisfiable.)
+on the path could be unsatisfiable.)
A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
among the correct decision trees for the given graph.
\lemman{Construction of optimal decision trees}\id{odtconst}%
An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
-the Pointer machine in time $\O(2^{2^{4n^2}})$.
+the Pointer Machine in time $\O(2^{2^{4n^2}})$.
\proof
We will try all possible decision trees of depth at most $2n^2$
The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
and each permutation can be checked in time $\O(\poly(n))$.
-On the Pointer machine, trees and permutations can be certainly enumerated in time
+On the Pointer Machine, trees and permutations can be certainly enumerated in time
$\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore
$\O(2^{2^{3n^2}} \cdot 2^{n^3} \cdot \poly(n)) = \O(2^{2^{4n^2}})$.
\qed
$\msf(G) = \bigcup_i \msf(C_i)$ for every permutation of edge weights.
\lemma\id{partiscomp}%
-The subgraphs $C_1,\ldots,C_k$ generated by the Partition procedure of the
+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$.
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
-(\ref{cyclerule}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
+(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~subgraph~$C_i$ such that it contains
-an~edge~$e$ of~$K$ and all subgraphs constructed later by the procedure do not contain
+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 subgraphs, there can be at most one edge from~$K$ adjacent to the maximal path,
+earlier clusters, there can be at most one edge from~$K$ adjacent to the maximal path,
which is impossible.
\qed
\qed
\cor\id{dtpart}%
-If $C_1,\ldots,C_k$ are the subgraphs generated by the Partition procedure (Algorithm \ref{partition}),
+If $C_1,\ldots,C_k$ are the clusters generated by the Partition procedure (Algorithm \ref{partition}),
then $D(\bigcup_i C_i) = \sum_i D(C_i)$.
\proof
We will describe the algorithm as a~recursive procedure. When the procedure is
called on a~graph~$G$, it sets the parameter~$t$ to roughly $\log^{(3)} n$ and
it calls the \<Partition> procedure to split the graph into a~collection of
-subgraphs of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision
-trees to find the MSF of the subgraphs. The graph obtained by contracting
-the subgraphs 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 subgraphs
+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
\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 subgraphs}
+\:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}
\:Call \<Partition> (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
- a~collection~$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges.
+ 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 iterations of the Contractive Bor\o{u}vka's algorithm (\ref{contbor}) on~$G_B$,
+\: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$.
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.
+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:
disposal.
By the Partitioning theorem (\ref{partthm}), the call to \<Partition> with~$\varepsilon$
-set to a~constant takes $\O(m)$ time and it produces a~collection of subgraphs of size
+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 subgraphs in~$\C$ with isolated vertices, so that they
+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 subgraphs in time:
+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 subgraph~$C_i$ then takes $\O(D(C_i))$ steps.
+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
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 iterations of the Bor\o{u}vka's algorithm on~$G_B$ take $\O(m)$
+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
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
+The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot a(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$
projects / saga.git / blobdiff