X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=opt.tex;h=9de4d64a617cfd05943cdd07d4f3c0c29663d661;hb=13caeb89ef8876aaa087925f238e5f8252e1ce29;hp=2d76688c9c20bcf3b16b9d02c3e1e5ea0f378f3f;hpb=9986fbd5d1ee200de6876128901a31884ce88b4a;p=saga.git diff --git a/opt.tex b/opt.tex index 2d76688..9de4d64 100644 --- a/opt.tex +++ b/opt.tex @@ -532,10 +532,10 @@ 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~traditional heap. The most efficient specimen of a~heap-based +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 +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 @@ -555,11 +555,11 @@ 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. +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$ edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints +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}% @@ -574,15 +574,18 @@ 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 that we can write $G=C \cup (G/C)$. +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)$. We know that the edges that +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, \ref{cyclerule}). @@ -592,14 +595,14 @@ 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$ adjacent to~$c$ on this cycle. +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 ready to bring corruption back to the game now and state a~``robust'' version +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}% @@ -609,12 +612,12 @@ some of the edges in~$R$. As usually, we will assume that all edges of this grap have pairwise distinct weights. 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)$). +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 of edges~$R$. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$. +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 @@ -628,31 +631,31 @@ If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $g$~is the he 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~$(G\crpt R)\cup C$ such that all edges of~$P$ are lighter than $e$ or~$f$ and hence +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 -Our plan still is 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 which got corrupted in the process. +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 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 as follows: +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.} \: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$ in it. +\::\ 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$. @@ -660,42 +663,43 @@ We can formulate the exact partitioning algorithm as follows: \:::$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.} \::\ the heap and add all remaining corrupted edges to~$K$. -\::$R^\C\=R^\C \cup \{ K^T \}$. \cmt{Record the ``interesting'' corrupted edges.} +\::$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. A~tree is built from edges adjacent to live vertices +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 of~$R^\C$ are immediately deleted from the graph, so they never participate +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 only if all vertices are dead, so each vertex must have +Claim~2: The algorithm stops when all vertices are dead, so each vertex must have entered some tree. -Claim~3: 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. +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 gathers @@ -704,8 +708,8 @@ size of the component), or the heap becomes empty (which means that the tree spa 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 -in every direction, the heaps can corrupt at worst $2\varepsilon m$ edges altogether. +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 @@ -715,22 +719,22 @@ $$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\biggl( \bigl(G / \bigcup_i C_i \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 2$. -\:$D(m',n') \ge D(m,n)$ whenever $m'\ge m, n'\ge n$. +\:$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 the edge has the lowest of all weights (and +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). @@ -892,7 +897,7 @@ 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 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$. @@ -904,17 +909,17 @@ is the union of the MSF's of the individual compartments. By the Cycle rule 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 components, 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 \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 from distinct compartments. +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)$ @@ -943,19 +948,19 @@ A~collection of decision trees for the individual compartments can be ``glued to to a~decision tree for~$G$. We take the decision tree for~$C_1$, replace every its leaf by a~copy of the tree for~$C_2$ and so on. Every leaf~$\ell$ of the compound tree will be labeled with the union of labels of the original leaves encountered on the path from -the root to the new leaf~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$. +the root to~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$. The other inequality requires more effort. We use the previous lemma to transform the optimal decision tree for~$G$ to another of the same depth, but without inter-compartment comparisons. Then we prove by induction on~$k$ and then on the depth of the tree -that the tree can be re-arranged, so that every computation first compares edges +that this tree can be re-arranged, so that every computation first compares edges from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed -to decision trees for the $C_i$'s and without loss of generality all trees for -a~single~$C_i$ can be made isomorphic. +to decision trees for the $C_i$'s. Also, without loss of generality all trees for +a~single~$C_i$ can be made isomorphic to~${\cal D}(C_i)$. \qed \cor\id{dtpart}% -If $C_1,\ldots,C_k$ are the 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 @@ -978,30 +983,31 @@ Taking a~maximum over all choices of~$G$ yields $D(2m,2n) \ge \max_G D(G_2) = 2D \section{An optimal algorithm}\id{optalgsect}% Once we have developed the soft heaps, partitioning and MST decision trees, -it is now simple to state the Pettie's and Ramachandran's MST algorithm \cite{pettie:optimal} +it is now simple to state the Pettie's and Ramachandran's MST algorithm and prove that it is asymptotically optimal among all MST algorithms in comparison-based models. Several standard MST algorithms from the previous -chapters will play their roles. +chapters will also play their roles. We will describe the algorithm as a~recursive procedure. When the procedure is -called on a~graph~$G$, it sets the parameter~$t$ to rougly $\log^{(3)} n$ and +called on a~graph~$G$, it sets the parameter~$t$ to roughly $\log^{(3)} n$ and it calls the \ 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 small 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. The resulting graph will have both the number of -vertices and edges reduced by a~constant factor and we recurse on it. +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\=\lceil\log^{(3)} n\rceil$. \cmt{the size of subgraphs} +\:$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 subgraphs and a~set~$R^\C$ of corrupted edges. -\:$F_i \= \mst(C_i)$ for all~$i$ obtained using optimal decision trees. + 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} @@ -1021,7 +1027,7 @@ The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following re $$ 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 constants and $D$~is the decision tree complexity +where~$c_1$ and~$c_2$ are some positive constants and $D$~is the decision tree complexity from the previous section. \proof @@ -1029,22 +1035,24 @@ 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 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 -have exactly~$t$ vertices. We define the computation so that it labels the graph with a~pointer to +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: -$$\O\Bigl(\Vert\C\Vert + t^{t(2t+1)} \cdot \bigl(2^{2^{4t^2}} + t^2\bigr)\Bigr) = \O(m).$$ -Execution of the decision tree on each subgraph~$C_i$ then takes $\O(D(C_i))$ steps. +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 +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 @@ -1061,8 +1069,9 @@ or in case of the contractions by the bucket-sorting techniques of Section \ref{ \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 the -decision tree complexity $D(m,n)$ itself. This way, we prove the following theorem: +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))$. @@ -1076,14 +1085,15 @@ case is trivial, for the induction step we will expand on the previous lemma: $$\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(m,n) + T(m/2, n/4) + c_2m &(Corollary \ref{dtpart})\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 for +The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound on the time complexity of every comparison-based algorithm. \qed @@ -1092,24 +1102,24 @@ As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST is still open and so is therefore 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 for the optimal algorithm. +as an~upper bound on the optimal algorithm. The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$. 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 section --- in particular the soft heaps and robust contractions. -The algorithm is unfortunately very complex and it involves a~lot of elaborate -technical details, so we will only refer to the original paper here. Another algorithm of the same -complexity, based on 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 only +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} -The time complexity of the Optimal MST algorithm is bounded by $\O(m\timesalpha(m,n))$. +The time complexity of the Optimal MST algorithm is $\O(m\timesalpha(m,n))$. \proof -Bound $D(m,n)$ by the number of comparisons performed by the algorithms of Chazelle \cite{chazelle:ackermann} +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 @@ -1130,8 +1140,8 @@ of oracle. Indeed, whatever trick we employ to achieve linear time complexity, w 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 already know that access to a~source -of random bits allows us to compute the MST in expected linear time (the KKT Algorithm, \ref{kkt}). +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.