From f5818d6a797fe8806c7aa32098a2e21b292afb67 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 27 Jan 2008 22:31:23 +0100 Subject: [PATCH] Iterated Jarnik. --- macros.tex | 1 + mst.tex | 145 +++++++++++++++++++++++++++++++++++++++++++++++---- notation.tex | 4 ++ 3 files changed, 139 insertions(+), 11 deletions(-) diff --git a/macros.tex b/macros.tex index eb4d4ee..3fc9efa 100644 --- a/macros.tex +++ b/macros.tex @@ -39,6 +39,7 @@ \def\mst{\mathop{\rm mst}} \def\deg{\mathop{\rm deg}} \def\timesalpha{\mskip2mu\alpha} +\def\tower{\mathop\uparrow} % Footnotes \newcount\footcnt diff --git a/mst.tex b/mst.tex index 9bde5ab..64a4921 100644 --- a/mst.tex +++ b/mst.tex @@ -870,7 +870,7 @@ active edge for~$w$ and replace it by~$vw$ if the new edge is lighter. The following algorithm shows how these operations translate to insertions, decreases and deletions on the heap. -\algn{Jarn\'\i{}k with active edges, Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}% +\algn{Jarn\'\i{}k with active edges; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}% \algo \algin A~graph~$G$ with an edge comparison oracle. \:$v_0\=$ an~arbitrary vertex of~$G$. @@ -889,7 +889,7 @@ and deletions on the heap. \endalgo \thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations -with the indicated amortized time complexity: +with the indicated amortized time complexities: \itemize\ibull \:\ (insertion of a~new element) in $\O(1)$, \:\ (decreasing value of an~existing element) in $\O(1)$, @@ -945,17 +945,139 @@ authors claim implementation advantages. \FIXME{Mention Thorup's Fibonacci-like heaps for integers?} -\rem -For sparse graphs, we can cross-breed this algorithm with the contractive -Bor\o{u}vka's algorithm: First perform $\log\log n$ steps of contractive -Bor\o{u}vka, which takes $\O(m\log\log n)$ time and produces a~graph~$G'$ -with $m'\le m$ and $n'\le n/\log n$. Then run Algorithm~\ref{jarniktwo} on~$G'$ -and it finishes in time $\O(m'+n'\log n') = \O(m)$. Finally combine MST edges -found by both algorithms to a~single tree as in~the Contraction lemma (\ref{contlemma}). +\para +As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time +for sufficiently dense graphs. In some cases, it is useful to combine it with +another MST algorithm, which identifies a~part of the MST edges and contracts +the graph to increase its density. For example, we can perform several +iterations of the Contractive Bor\o{u}vka's algorithm and find the rest of the +MST by the above version of Jarn\'\i{}k's algorithm. + +\algn{Mixed Bor\o{u}vka-Jarn\'\i{}k} +\algo +\algin A~graph~$G$ with an edge comparison oracle. +\:Run $\log\log n$ iterations of the Contractive Bor\o{u}vka's algorithm (\ref{contbor}), + getting a~MST~$T_1$. +\:Run the Jarn\'\i{}k's algorithm with active edges (\ref{jarniktwo}) on the resulting + graph, getting a~MST~$T_2$. +\:Combine $T_1$ and~$T_2$ to~$T$ as in the Contraction lemma (\ref{contlemma}). +\algout Minimum spanning tree~$T$. +\endalgo + +\thm +The Mixed Bor\o{u}vka-Jarn\'\i{}k algorithm finds the MST of the input graph in time $\O(m\log\log n)$. + +\proof +Correctness follows from the Contraction lemma and from the proofs of correctness of the respective algorithms. +As~for time complexity: The first step takes $\O(m\log\log n)$ time +(by Lemma~\ref{contiter}) and it gradually contracts~$G$ to a~graph~$G'$ of size +$m'\le m$ and $n'\le n/\log n$. The second step then runs in time $\O(m'+n'\log n') = \O(m)$ +and both trees can be combined in linear time, too. +\qed + +\para +Actually, there is a~much better choice of the algorithms to combine: use the +improved Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while. +The good choice of the stopping condition is to place a~limit on the size of the heap. +Start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large, +conserve the current tree and start with a~different vertex and an~empty heap. When this +process runs out of vertices, it has identified a~sub-forest of the MST, so we can +contract the graph along the edges of~this forest and iterate. + +\algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}} +\algo +\algin A~graph~$G$ with an edge comparison oracle. +\:$T\=\emptyset$. \cmt{edges of the MST} +\:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually} +\:$m_0\=m$. +\:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.} +\::$F\=\emptyset$. \cmt{forest built in the current phase} +\::$t\=2^{2m_0/n}$. \cmt{the limit on the heap size} +\::While there is a~vertex $v_0\not\in F$: +\:::Run the improved Jarn\'\i{}k's algorithm (\ref{jarniktwo}) from~$v_0$, stop when: +\::::all vertices have been processed, or +\::::a~vertex of~$F$ has been added to the tree, or +\::::the heap had more than~$t$ elements. +\:::Denote the resulting tree~$R$. +\:::$F\=F\cup R$. +\::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.} +\::Contract~$G$ along all edges of~$F$ and flatten it. +\algout Minimum spanning tree~$T$. +\endalgo + +\nota +For analysis of the algorithm, let us denote the graph entering the $i$-th +phase by~$G_i$ and likewise with the other parameters. The trees from which +$F_i$~has been constructed will be called $R_i^1, \ldots, R_i^{z_i}$. The +non-indexed $G$, $m$ and~$n$ will correspond to the graph given as~input. + +\para +However the choice of the parameter~$t$ can seem mysterious, the following +lemma makes the reason clear: -\para Xyzzy. +\lemma +The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m_i)$. + +\proof +During the phase, the heap always contains at most~$t_i$ elements, so it takes +time~$\O(\log t_i)=\O(m/n_i)$ to delete an~element from the heap. The trees~$R_i^j$ +are disjoint, so there are at most~$n_i$ \'s over the course of the phase. +Each edge is considered at most twice (once per its endpoint), so the number +of the other heap operations is~$\O(m_i)$. Together, it equals $\O(m_i + n_i\log t_i) = \O(m_i)$. +\qed + +\lemma +Unless the $i$-th phase is final, the forest~$F_i$ consists of at most $2m_i/t_i$ trees. -\FIXME{Describe the heap limitation trick and the $\O(m\beta(m,n))$ algorithm.} +\proof +As every edge of~$G_i$ is incident with at most two such trees, it is sufficient +to establish that there are at least~$t_i$ edges incident with the vertices of every +such tree~(*). + +The forest~$F_i$ evolves by additions of the trees~$R_i^j$. There are three possibilities +how the algorithm could have stopped growing the tree~$R_i^j$: +\itemize\ibull +\:the heap had more than~$t_i$ elements (step~10): since the elements stored in the heap correspond + to some of the edges incident with vertices of~$R_i^j$, the condition~(*) is fulfilled; +\:the algorithm just added a~vertex of~$F_i$ to~$R_i^j$ (step~9): in this case, an~existing + tree of~$F_i$ is extended, so the number of edges incident with it cannot decrease;\foot{% + To make this true, we counted the edges incident with the \em{vertices} of the tree + instead of edges incident with the tree itself, because we needed the tree edges + to be counted as well.} +\:all vertices have been processed (step~8): this can happen only in the final phase. +\endlist +\>In all three cases, there are sufficiently many incident edges. +\qed + +\thm\id{itjarthm}% +The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time +$\O(m\mathop\beta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n < m/n \}$. + +\proof +Phases are finite and in every phase at least one edge is contracted, so the outer +loop is eventually terminated. The resulting subgraph~$T$ is equal to $\mst(G)$, because each $F_i$ is +a~subgraph of~$\mst(G_i)$ and the $F_i$'s are glued together according to the Contraction +lemma (\ref{contlemma}). + +Let us bound the sizes of the graphs processed in individual phases. As the vertices +of~$G_{i+1}$ correspond to the components of~$F_i$, by the previous lemma $n_{i+1}\le +2m_i/t_i$. Then $t_{i+1} = 2^{2m/n_{i+1}} \ge 2^{2m/(2m_i/t_i)} = 2^{(m/m_i)\cdot t_i} \ge 2^{t_i}$, +therefore: +$$ +t_i \ge 2^{2^{2^{\vdots^{m/n}}}} +$$ +and as soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time +there is enough space in the heap to process the whole graph. +\qed + +\FIXME{The notation is clumsy and so is the proof, at least typographically.} + +\cor +The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$. + +\proof +$\beta(m,n) \le \beta(1,n) = \log^* n$. +\qed @@ -969,5 +1091,6 @@ found by both algorithms to a~single tree as in~the Contraction lemma (\ref{cont % impedance mismatch in terminology: contraction of G along e vs. contraction of e. % use \delta(X) notation % mention disconnected graphs +% unify use of n(G) vs. n \endpart diff --git a/notation.tex b/notation.tex index 0da0035..12cf520 100644 --- a/notation.tex +++ b/notation.tex @@ -36,6 +36,10 @@ \n{${\bb E}X$}{expected value of a~random variable~$X$} \n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true} \n{$\log n$}{a binary logarithm of the number~$n$} +\n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$} +\n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$} +\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n < 1\}$; the inverse of~$2\tower n$} +\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n < m/n \}$ \[itjarthm]} } \section{Multigraphs and contractions} -- 2.39.5