From 6e1c4a014781bb45b7714508459412afece67d63 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 21 Jan 2008 18:09:44 +0100 Subject: [PATCH] Finished the section on minor-closed classes. --- macros.tex | 5 +- mst.tex | 136 +++++++++++++++++++++++++++++++++++++++++++++++---- notation.tex | 5 +- 3 files changed, 133 insertions(+), 13 deletions(-) diff --git a/macros.tex b/macros.tex index 42b162d..b0df97e 100644 --- a/macros.tex +++ b/macros.tex @@ -36,12 +36,13 @@ \def\symdiff{\mathbin{\Delta}} \def\hphantas#1#2{\setbox0=\hbox{#2}\hbox to \wd0{#1\hss}} \def\o#1{\accent23 #1} -\def\mst{{\rm mst}} +\def\mst{\mathop{\rm mst}} +\def\deg{\mathop{\rm deg}} % Footnotes \newcount\footcnt \footcnt=0 -\def\foot#1{\global\advance\footcnt by 1{\parindent=0.25in\parskip=0pt\footnote{$^{\the\footcnt}$}{#1}}} +\def\foot#1{\global\advance\footcnt by 1{\parindent=0.25in\parskip=0pt\footnote{$^{\bf\the\footcnt}$}{#1}}} %%% Fonts %%% diff --git a/mst.tex b/mst.tex index e8ec543..58a8d5f 100644 --- a/mst.tex +++ b/mst.tex @@ -218,7 +218,7 @@ is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$. Most MST algorithms can be described as special cases of the following procedure (again following \cite{tarjan:dsna}): -\algn{Red-Blue Meta-Algorithm} +\algn{Red-Blue Meta-Algorithm}\id{rbma}% \algo \algin A~graph $G$ with an edge comparison oracle (see \ref{edgeoracle}) \:In the beginning, all edges are colored black. @@ -502,7 +502,7 @@ formulations and proofs, which we preferred to avoid. We also note that most of the algorithms can be run on disconnected multigraphs with little or no modifications. -\algn{Contractive version of Bor\o{u}vka's algorithm} +\algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor} \algo \algin A~graph~$G$ with an edge comparison oracle. \:$T\=\emptyset$. @@ -515,7 +515,7 @@ modifications. \algout Minimum spanning tree~$T$. \endalgo -\lemma +\lemma\id{contiter}% Each iteration of the algorithm can be carried out in time~$\O(m)$. \proof @@ -539,9 +539,9 @@ As in the original Bor\o{u}vka's algorithm, the number of phases is $\O(\log n)$ Then apply the previous lemma. \qed -\thmn{\cite{mm:mst}} +\thmn{\cite{mm:mst}}\id{planarbor}% When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in -time $\O(m)$. +time $\O(n)$. \proof Let us denote the graph considered by the algorithm at the beginning of the $i$-th @@ -559,7 +559,7 @@ However, every $G_i$ is planar, because the class of planar graphs is closed under edge deletion and contraction. The~$G_i$ is also simple as we explicitly removed multiple edges and loops at the end of the previous iteration. So we can use the standard theorem on the number of edges of planar simple graphs (see for example \cite{diestel:gt}) to get $m_i\le 3n_i \le 3n/2^i$. -From this we get that the total time complexity is $\O(\sum_i m_i)=\O(m)$. +From this we get that the total time complexity is $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$. \qed \rem @@ -587,7 +587,7 @@ define the order of vertices (which can be arbitrary, but has to be fixed). Graph contractions are indeed a~very powerful tool and they can be used in other MST algorithms as well. The following lemma shows the gist: -\lemman{Contraction of MST edges}% +\lemman{Contraction of MST edges}\id{contlemma}% Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph produced by contracting $G$ along~$e$, and $\pi$ the bijection between edges of~$G-e$ and their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$ @@ -662,7 +662,7 @@ It has $a\cdot 2^k = \Theta(n)$ vertices and ${a \choose 2} + a\cdot 2^k = \Thet as we wanted. By the previous lemma, the algorithm proceeds through a sequence of hedgehogs $H_{a,k}, -H_{a,k-1}, \ldots, H_{a,0}$, so it needs a logarithmic number of iterations plus some more +H_{a,k-1}, \ldots, H_{a,0}$ (up to monotone isomorphism), so it needs a logarithmic number of iterations plus some more to finish on the remaining complete graph. Each iteration runs on a graph with $\Omega(n)$ edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices. \qed @@ -673,7 +673,7 @@ The contracting algorithm given in the previous section has been found to perfor well on planar graphs, but in the general case its time complexity was not linear. Can we find some broader class of graphs where the algorithm is still efficient? The right context turns out to be the minor-closed graph classes, which are -closed on contractions and have bounded density. +closed under contractions and have bounded density. \defn A~graph~$H$ is a \df{minor} of a~graph~$G$ iff it can be obtained @@ -691,7 +691,7 @@ to these classes, too, most notable the linearity of the number of edges. \defn\id{density}% Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$ -to be the infimum of all~$\varrho$'s such that $\vert E(G) \vert \le \varrho\cdot\vert V(G)\vert$ +to be the infimum of all~$\varrho$'s such that $m(G) \le \varrho\cdot n(G)$ holds for every $G\in\cal C$. \thmn{Density of minor-closed classes} @@ -702,6 +702,121 @@ a non-trivial class. See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions. \qed +\thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}% +For any fixed non-trivial minor-closed class~$\cal C$ of graphs, Algorithm \ref{contbor} finds +the MST of any graph from this class in time $\O(n)$. (The constant hidden in the~$\O$ +depends on the class.) + +\proof +Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered +by the algorithm at the beginning of the $i$-th iteration by~$G_i$ and its number of vertices +and edges by $n_i$ and $m_i$ respectively. Again the $i$-th phase runs in time $\O(m_i)$ +and $n_i \le n/2^i$, so it remains to show a linear bound for the $m_i$'s. + +Since each $G_i$ is produced from~$G_{i-1}$ by a sequence of edge contractions, +all $G_i$'s are minors of~$G$.\foot{Technically, these are multigraph contractions, +but followed by flattening, so they are equivalent to contractions on simple graphs.} +So they also belong to~$\cal C$ and by the previous theorem $m_i\le \varrho({\cal C})n_i$. +\qed + +\rem\id{nobatch}% +The contractive algorithm uses ``batch processing'' to perform many contractions +in a single step. It is also possible to perform contractions one edge at a~time, +batching only the flattenings. A~contraction of an edge~$uv$ can be performed +in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back +with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small +degrees. The following lemma shows that this is always the case in minor-closed +classes. + +\lemman{Low-degree vertices}\id{lowdeg}% +Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph +with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$. + +\proof +Assume the contrary: let there be at least $n/2$ vertices with degree +greater than~$4\varrho$. Then $\sum_v \deg(v) > n/2 +\cdot 4\varrho = 2\varrho n$, which is in contradiction with the number +of edges being at most $\varrho n$. +\qed + +\rem +The proof can be also viewed +probabilistically: let $X$ be the degree of a vertex of~$G$ chosen uniformly at +random. Then ${\bb E}X \le 2\varrho$, hence by the Markov's inequality +${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have +$\deg(v)\le 4\varrho$. + +\algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}% +\algo +\algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t$. +\:$T\=\emptyset$. +\:$\ell(e)\=e$ for all edges~$e$. +\:While $n(G)>1$: +\::While there exists a~vertex~$v$ such that $\deg(v)\le t$: +\:::Select the lightest edge~$e$ incident with~$v$. +\:::Contract~$G$ along~$e$. +\:::$T\=T\cup \{ \ell(e_i) \}$. +\::Flatten $G$, removing parallel edges and loops. +\algout Minimum spanning tree~$T$. +\endalgo + +\thm +When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the +Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$ +finds the MST of any graph from this class in time $\O(n)$. (The constant +in the~$\O$ depends on~the class only.) + +\proof +Let us denote by $G_i$, $n_i$ and $m_i$ the graph considered by the +algorithm at the beginning of the $i$-th iteration of the outer loop, +and the number of its vertices and edges respectively. As in the proof +of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s +are minors of the graph~$G$ given as the input. + +For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg}) +guarantees that at least $n_i/2$ edges get selected in the $i$-th iteration. +Hence at least a half of the vertices participates in contractions, so +$n_i\le 3/4\cdot n_{i-1}$. Therefore $n_i\le n\cdot (3/4)^i$ and the algorithm terminates +after $\O(\log n)$ iterations. + +Each selected edge belongs to $\mst(G)$, because it is the lightest edge of +the trivial cut separating~$v$ from the rest of the graph (see the Blue +Rule in \ref{rbma}). The steps 6 and~7 therefore correspond to the operation +described by the Lemma on contraction of MST edges (\ref{contlemma}) and when +the algorithm stops, $T$~is indeed the minimum spanning tree. + +It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have +$m_i\le \varrho n_i \le \varrho n/2^i$. +We will show that the $i$-th iteration is carried out in time $\O(m_i)$. +Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed +over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$. +Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting +Bor\o{u}vka's Algorithm (see \ref{contiter}). + +The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$. +\qed + +\rem +For planar graphs, we can get a sharper version of the low-degree lemma, +showing that the algorithm works with $t=8$ as well (we got $t=12$ from the +general version). While this does not change the asymptotic time complexity +of the algorithm, the constant-factor speedup can still delight the hearts of +its practical users. + +\lemman{Low-degree vertices in planar graphs}% +Let $G$ be a planar graph with $n$~vertices. Then at least $n/2$ vertices of~$v$ +have degree at most~8. + +\proof +It suffices to show that the lemma holds for triangulations (if there +are any edges missing, the situation can only get better) with at +least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$. +The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$, +hence by the same argument as in the previous proof, for at least $n/2$ +vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$. +\qed + + \section{Using Fibonacci heaps} @@ -713,5 +828,6 @@ See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalen % sorted weights % \O(...) as a set? % impedance mismatch in terminology: contraction of G along e vs. contraction of e. +% use \delta(X) notation \endpart diff --git a/notation.tex b/notation.tex index 4b3bd1f..304edb3 100644 --- a/notation.tex +++ b/notation.tex @@ -20,13 +20,16 @@ \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm} \n{MST}{minimum spanning tree \[mstdef]} \n{MSF}{minimum spanning forest \[mstdef]} -\n{\mst(G)}{the unique minimum spanning tree of a graph~$G$ \[mstnota]} +\n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]} \n{$X \choose k$}{a set of $k$-element subsets of a set~$X$} \n{$G/e$}{multigraph contraction \[contract]} \n{$G.e$}{simple graph contraction \[simpcont]} \n{$\alpha(n)$}{the inverse Ackermann's function} \n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$.} \n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]} +\n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context} +\n{${\bb E}X$}{expected value of a~random variable~$X$} +\n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true} } \section{Multigraphs and contractions} -- 2.39.2