X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=mst.tex;h=7e5be9097813a4ab59f639eaa4c520afab9527d8;hb=22844d1c9fa8e94db9206bd4f55e4d34de3de9b0;hp=a04c08002c3840233b9da362e2b8aee74833ecbb;hpb=98322f14d6ed8bb0e79dbb95e2c45b7b4617d664;p=saga.git diff --git a/mst.tex b/mst.tex index a04c080..7e5be90 100644 --- a/mst.tex +++ b/mst.tex @@ -20,7 +20,7 @@ in contemporary terminology: \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$, find its minimum spanning tree, defined as follows: -\defn\thmid{mstdef}% +\defn\id{mstdef}% For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$: \itemize\ibull \:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$. @@ -42,7 +42,7 @@ disciplines, the previous work was not well known and the algorithms had to be rediscovered several times. Recently, several significantly faster algorithms were discovered, most notably the -$\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and +$\O(m\timesbeta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}. @@ -51,7 +51,9 @@ and Pettie \cite{pettie:ackermann}. This chapter attempts to survery the important algorithms for finding the MST and it also presents several new ones. -\section{Basic Properties} +%-------------------------------------------------------------------------------- + +\section{Basic properties} In this section, we will examine the basic properties of spanning trees and prove several important theorems to base the algorithms upon. We will follow the theory @@ -65,7 +67,7 @@ First of all, let us show that the weights on edges are not necessary for the definition of the MST. We can formulate an equivalent characterization using an ordering of edges instead. -\defnn{Heavy and light edges}\thmid{heavy}% +\defnn{Heavy and light edges}\id{heavy}% Let~$T$ be a~spanning tree. Then: \itemize\ibull \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$. @@ -80,7 +82,7 @@ Let~$T$ be a~spanning tree. Then: Please note that the above properties also apply to tree edges which by definition cover only themselves and therefore they are always heavy. -\lemman{Light edges}\thmid{lightlemma}% +\lemman{Light edges}\id{lightlemma}% Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$ is not minimum. @@ -92,7 +94,7 @@ connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T') = w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum. \qed -\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}} +\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\ref{lightlemma}} The converse of this lemma is also true and to prove it, we will once again use technique of transforming trees by \df{exchanges} of edges. In the proof of the @@ -101,7 +103,7 @@ a spanning tree for another edge~$f$ covered by~$e$, the result is again a spanning tree. In fact, it is possible to transform any spanning tree to any other spanning tree by a sequence of exchanges. -\lemman{Exchange property for trees}\thmid{xchglemma}% +\lemman{Exchange property for trees}\id{xchglemma}% Let $T$ and $T'$ be spanning trees of a common graph. Then there exists a sequence of edge exchanges which transforms $T$ to~$T'$. More formally, there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that @@ -117,9 +119,9 @@ tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the inductio hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence. \qed -\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}} +\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\ref{xchglemma}} -\lemman{Monotone exchanges}\thmid{monoxchg}% +\lemman{Monotone exchanges}\id{monoxchg}% Let $T$ be a spanning tree such that there are no $T$-light edges and $T'$ be an arbitrary spanning tree. Then there exists a sequence of edge exchanges transforming $T$ to~$T'$ such that the weight does not increase in any step. @@ -144,15 +146,15 @@ $w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter than~$e'$ as $e'$ was not $T$-light. \qed -\thm\thmid{mstthm}% +\thmn{Minimality by order}\id{mstthm}% A~spanning tree~$T$ is minimum iff there is no $T$-light edge. \proof -If~$T$ is minimum, then by Lemma~\thmref{lightlemma} there are no $T$-light +If~$T$ is minimum, then by Lemma~\ref{lightlemma} there are no $T$-light edges. Conversely, when $T$ is a spanning tree without $T$-light edges and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone -exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence +exchange lemma (\ref{monoxchg}) there exists a non-decreasing sequence of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$ and thus $T$~is also minimum. \qed @@ -163,20 +165,20 @@ minimum spanning trees according to the Cayley's formula \cite{cayley:trees}). However, as the following theorem shows, this is possible only if the weight function is not injective. -\thmn{MST uniqueness} +\thmn{MST uniqueness}% If all edge weights are distinct, then the minimum spanning tree is unique. \proof Consider two minimum spanning trees $T_1$ and~$T_2$. According to the previous theorem, there are no light edges with respect to neither of them, so by the -Monotone exchange lemma (\thmref{monoxchg}) there exists a sequence of non-decreasing +Monotone exchange lemma (\ref{monoxchg}) there exists a sequence of non-decreasing edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct, these edge exchanges must be in fact strictly increasing. On the other hand, we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed $T_1$ and $T_2$ must be identical. \qed -\rem\thmid{edgeoracle}% +\rem\id{edgeoracle}% To simplify the description of MST algorithms, we will expect that the weights of all edges are distinct and that instead of numeric weights (usually accompanied by problems with representation of real numbers in algorithms) we will be given @@ -187,18 +189,42 @@ minimum spanning trees, the unique MST of the new graph will still be a MST of t original graph. In the few cases where we need a more concrete input, we will explicitly state so. -\nota\thmid{mstnota}% +\nota\id{mstnota}% When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote its unique minimum spanning tree. -\section{The Red-Blue Meta-Algorithm} +Another useful consequence is that whenever two graphs are isomorphic and the +isomorphism preserves weight order, the isomorphism applies to their MST's +as well: + +\defn +A~\df{monotone isomorphism} of two weighted graphs $G_1=(V_1,E_1,w_1)$ and +$G_2=(V_2,E_2,w_2)$ is a bijection $\pi: V_1\rightarrow V_2$ such that +for each $u,v\in V_1: uv\in E_1 \Leftrightarrow \pi(u)\pi(v)\in E_2$ and +for each $e,f\in E_1: w_1(e)w(e_2)>\ldots>w(e_k)>w(e_1)$, -which is a contradiction. (Note that distinctness of edge weights was crucial here.) +or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation +of the cycle). Then $e_2=v_2u_3$ and $w(e_2)w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction. +(Note that distinctness of edge weights was crucial here.) \qed -\lemma\thmid{boruvkadrop}% -In each iteration of the algorithm, the number of trees in~$T$ drops at least twice. - -\proof -Each tree gets merged with at least one neighboring trees, so each of the new trees -consists of at least two original trees. -\qed - -\cor -The algorithm stops in $\O(\log n)$ iterations. - -\lemma\thmid{boruvkaiter}% +\lemma\id{boruvkaiter}% Each iteration can be carried out in time $\O(m)$. \proof -Following \cite{mm:mst}, -we assign a label to each tree and we keep a mapping from vertices to the +We assign a label to each tree and we keep a mapping from vertices to the labels of the trees they belong to. We scan all edges, map their endpoints to the particular trees and for each tree we maintain the lightest incident edge so far encountered. Instead of merging the trees one by one (which would be too -slow), we build an auxilliary graph whose vertices are labels of the original +slow), we build an auxilliary graph whose vertices are the labels of the original trees and edges correspond to the chosen lightest inter-tree edges. We find connected -components of this graph, these determine how the original labels are translated +components of this graph, these determine how are the original labels translated to the new labels. \qed @@ -344,10 +372,10 @@ Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$. Follows from the previous lemmata. \qed -\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}} +\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}% \algo \algin A~graph~$G$ with an edge comparison oracle. -\:$T\=$ a single-vertex tree containing any vertex of~$G$. +\:$T\=$ a single-vertex tree containing an~arbitrary vertex of~$G$. \:While there are vertices outside $T$: \::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$. \::$T\=T+uv$. @@ -355,18 +383,19 @@ Follows from the previous lemmata. \endalgo \lemma -Jarn\'\i{}k's algorithm returns the MST of the input graph. +Jarn\'\i{}k's algorithm computers the MST of the input graph. \proof -During the course of the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying -the Blue rule to a cut between~$T$ and the rest of the given graph. We need not care about +If~$G$ is connected, the algorithm always stops. Let us prove that in every step of +the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying +the Blue rule to the cut $\delta(T)$ separating~$T$ from the rest of the given graph. We need not care about the remaining edges, since for a connected graph the algorithm always stops with the right number of blue edges. \qed \impl The most important part of the algorithm is finding \em{neighboring edges,} i.e., edges -going between $T$ and $V(G)\setminus T$. In the straightforward implementation, +of the cut $\delta(T)$. In a~straightforward implementation, searching for the lightest neighboring edge takes $\Theta(m)$ time, so the whole algorithm runs in time $\Theta(mn)$. @@ -380,10 +409,10 @@ at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time i From this, we can conclude: \thm -Jarn\'\i{}k's algorithm finds the MST of the graph in time $\O(m\log n)$. +Jarn\'\i{}k's algorithm finds the MST of a~given graph in time $\O(m\log n)$. \rem -We will show several faster implementations in section \secref{fibonacci}. +We will show several faster implementations in section \ref{fibonacci}. \algn{Kruskal \cite{kruskal:mst}, the Greedy algorithm} \algo @@ -401,21 +430,24 @@ Kruskal's algorithm returns the MST of the input graph. \proof In every step, $T$ is a forest of blue trees. Adding~$e$ to~$T$ -in step~4 applies the Blue rule on the cut separating two components of~$T$ ($e$ is the lightest, +in step~4 applies the Blue rule on the cut separating some pair of components of~$T$ ($e$ is the lightest, because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds -to the red rule on the cycle found ($e$~must be the heaviest, since all other edges of the -cycle have been already processed). At the end of the algorithm, all edges have been colored, +to the Red rule on the cycle found ($e$~must be the heaviest, since all other edges of the +cycle have been already processed). At the end of the algorithm, all edges are colored, so~$T$ must be the~MST. \qed \impl -Except for the initial sorting, which in general takes $\Theta(m\log n)$ time, the only -other non-trivial operation is detection of cycles. What we need is a data structure +Except for the initial sorting, which in general takes $\Theta(m\log m)$ time, the only +other non-trivial operation is the detection of cycles. What we need is a data structure for maintaining connected components, which supports queries and edge insertion. -The following theorem shows that it can be done with a surprising efficiency. +(This is also known under the name Disjoint Set Union problem, i.e., maintenance +of an~equivalence relation on a~set with queries on whether two elements are equivalent +and the operation of joining two equivalence classes into one.) +The following theorem shows that it can be done with surprising efficiency. -\thmn{Incremental connectivity} -When only edge insertions and queries are allowed, connected components +\thmn{Incremental connectivity}% +When only edge insertions and connectivity queries are allowed, connected components can be maintained in $\O(\alpha(n))$ time amortized per operation. \proof @@ -433,13 +465,15 @@ corresponding components and always recolor the smaller of the two components. \thm Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$ -or $\O(m\alpha(n))$ if the edges are already sorted by their weights. +or $\O(m\timesalpha(n))$ if the edges are already sorted by their weights. \proof Follows from the above analysis. \qed -\section{Contractive algorithms} +%-------------------------------------------------------------------------------- + +\section{Contractive algorithms}\id{contalg}% While the classical algorithms are based on growing suitable trees, they can be also reformulated in terms of edge contraction. Instead of keeping @@ -454,33 +488,32 @@ a linear-time algorithm for MST in planar graphs. There are two definitions of edge contraction which differ when an edge of a triangle is contracted. Either we unify the other two edges to a single edge -or we keep them as two parallel edges, leaving us with a multigraph. We will -use the multigraph version and show that we can easily reduce the multigraph -to a simple graph later. (See \thmref{contract} for the exact definitions.) +or we keep them as two parallel edges, leaving us with a~multigraph. We will +use the multigraph version and we will show that we can easily reduce the multigraph +to a simple graph later. (See \ref{contract} for the exact definitions.) We only need to be able to map edges of the contracted graph to the original -edges, so each edge will carry a unique label $\ell(e)$ which will be preserved by +edges, so each edge will carry a unique label $\ell(e)$ that will be preserved by contractions. -\lemman{Flattening a multigraph}\thmid{flattening}% +\lemman{Flattening a multigraph}\id{flattening}% Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been removed and each bundle of parallel edges replaced by its lightest edge. Then $G'$~has the same MST as~$G$. \proof -Loops can be never used in a spanning tree. If there is a spanning tree~$T$ +Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction: +Loops can be never contained in a spanning tree. If there is a spanning tree~$T$ containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$ -for~$e$ in~$T$ makes it lighter. \qed +for~$e$ makes~$T$ lighter. \qed \rem Removal of the heavier of a pair of parallel edges can be also viewed as an application of the Red rule on a two-edge cycle. And indeed it is, the Red-Blue procedure works on multigraphs as well as on simple graphs and all the -classical algorithms also do. We only would have to be more careful in the -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. +classical algorithms also do. We would only have to be more careful in the +formulations and proofs, which we preferred to avoid. -\algn{Contracting 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$. @@ -488,17 +521,17 @@ modifications. \:While $n(G)>1$: \::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$. \::$T\=T\cup \{ \ell(e_i) \}$. \cmt{Remember labels of all selected edges.} -\::Contract $G$ along all edges $e_i$, inheriting labels and weights. +\::Contract $G$ along all edges $e_i$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.} \::Flatten $G$, removing parallel edges and loops. \algout Minimum spanning tree~$T$. \endalgo -\lemma +\lemma\id{contiter}% Each iteration of the algorithm can be carried out in time~$\O(m)$. \proof The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly -to the unions in the original Bor\o{u}vka's algorithm (see \thmref{boruvkaiter}). +to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}): We build an auxillary graph containing only the selected edges~$e_i$, find connected components of this graph and renumber vertices in each component to the identifier of the component. This takes $\O(m)$ time. @@ -510,61 +543,52 @@ $\O(n+m)=\O(m)$. \qed \thm -The Contracting Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$. +The Contractive Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$. \proof -As in the original Bor\o{u}vka's algorithm, the number of phases is $\O(\log n)$. +As in the original Bor\o{u}vka's algorithm, the number of iterations is $\O(\log n)$. Then apply the previous lemma. \qed -\thmn{\cite{mm:mst}} -When the input graph is planar, the Contracting Bor\o{u}vka's algorithm runs in -time $\O(m)$. +\thmn{\cite{mm:mst}}\id{planarbor}% +When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in +time $\O(n)$. \proof Let us denote the graph considered by the algorithm at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and its number of vertices and edges by $n_i$ and $m_i$ respectively. As we already know from the previous lemma, the $i$-th iteration takes $\O(m_i)$ time. We are going to prove that the -$m_i$'s are decreasing exponentially. +$m_i$'s are decreasing geometrically. -The number of trees in the non-contracting version of the algorithm decreases -at least twice in each iteration (Lemma \thmref{boruvkadrop}) and therefore the -same must hold for the number of vertices in the contracting version. So $n_i\le n/2^i$. +The number of trees in the non-contracting version of the algorithm drops +at least by a factor of two in each iteration (Lemma \ref{boruvkadrop}) and the +same must hold for the number of vertices in the contracting version. +Therefore $n_i\le n/2^i$. 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 +loops at the end of the previous iteration. Hence 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 -There are other possibilities how to find the MST of a planar graph in linear time. -Matsui \cite{matsui:planar} has described an algorithm based on simultaneously -processing the graph and its dual. The advantage of our approach is that we do not -need to construct the planar embedding first. +There are several other possibilities how to find the MST of a planar graph in linear time. +For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously +working on the graph and its topological dual. The advantage of our approach is that we do not need +to construct the planar embedding explicitly. We will show one more linear algorithm +in section~\ref{minorclosed}. \rem -To achieve the linear time complexity, the algorithm needs a very careful implementation. -Specifically, when we represent the graph using adjacency lists, whose heads are stored -in an array indexed by vertex identifiers, we must renumber the vertices in each iteration. -Otherwise, unused identifiers could end up taking most of space in the arrays and scans of these -arrays would have super-linear cost with respect to the size of the current graph~$G_i$. +To achieve the linear time complexity, the algorithm needs a very careful implementation, +but we defer the technical details to section~\ref{bucketsort}. -\rem -The algorithm can be also implemented on the pointer machine. Representation of graphs -by pointer structures easily avoids the aforementioned problems with sparse arrays, -but we need to handle the bucket sorting somehow. We can create a small data structure -for every vertex and use a pointer to this structure as a unique identifier of the vertex. -We will also keep a list of all vertex structures. During the bucket sort, each vertex -structure will contain a pointer to the corresponding bucket and the vertex list will -define the order of vertices (which can be arbitrary, but has to be fixed). - -Graph contractions are a very powerful tool and they can be used in other MST +\para +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.$$ @@ -572,30 +596,76 @@ their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$ \proof % We seem not to need this lemma for multigraphs... %If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the -%Flattening lemma (\thmref{flattening}), the MST stays the same and if we remove a parallel edge +%Flattening lemma (\ref{flattening}), the MST stays the same and if we remove a parallel edge %or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates %in a MST. The right-hand side of the equality is a spanning tree of~$G$, let us denote it by~$T$ and the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$ -(according to Theorem \thmref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$, +(by Theorem \ref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$, then $\pi[T[f]]$ is a path covered by~$\pi(f)$ in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path. In both cases, $f$ is $T'$-light, which contradicts the minimality of~$T'$. (We do not have -a multigraph version of the theorem, but this direction is a straightforward edge exchange, -which of course works in multigraphs as well.) +a~multigraph version of the theorem, but the side we need is a~straightforward edge exchange, +which obviously works in multigraphs as well.) \qed \rem In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$. -\section{Minor-closed graph classes} +Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity +is tight. The graphs do not have unique weights, but they are constructed in a way that +the algorithm never compares two edges with the same weight. Therefore, when two such +graphs are monotonely isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way. + +\defn +A~\df{distractor of order~$k$,} denoted by~$D_k$, is a path on $n=2^k$~vertices $v_1,\ldots,v_n$ +where each edge $v_iv_{i+1}$ has its weight equal to the number of trailing zeroes in the binary +representation of the number~$i$. The vertex $v_1$ is called a~\df{base} of the distractor. -\section{Using Fibonacci heaps} -\secid{fibonacci} +\rem +Alternatively, we can use a recursive definition: $D_0$ is a single vertex, $D_{k+1}$ consists +of two disjoint copies of~$D_k$ joined by an edge of weight~$k$. + +\figure{distractor.eps}{\epsfxsize}{A~distractor $D_3$ and its evolution (bold edges are contracted)} + +\lemma +A~single iteration of the contractive algorithm reduces~$D_k$ to a graph isomorphic with~$D_{k-1}$. -% G has to be connected, so m=O(n) -% mention Steiner trees -% mention matroids -% sorted weights -% \O(...) as a set? +\proof +Each vertex~$v$ of~$D_k$ is incident with a single edge of weight~1. The algorithm therefore +selects all weight~1 edges and contracts them. This produces a graph which is +exactly $D_{k-1}$ with all weights increased by~1, which does not change the relative order of edges. +\qed + +\defn +A~\df{hedgehog}~$H_{a,k}$ is a graph consisting of $a$~distractors $D_k^1,\ldots,D_k^a$ of order~$k$ +together with edges of a complete graph on the bases of the distractors. These additional edges +have arbitrary weights, but heavier than the edges of all distractors. + +\figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)} + +\lemma +A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a graph isomorphic with $H_{a,k-1}$. + +\proof +Each vertex is incident with an edge of some distractor, so the algorithm does not select +any edge of the complete graph. Contraction therefore reduces each distractor to a smaller +distractor (modulo an additive factor in weight) and leaves the complete graph intact. +This is monotonely isomorphic to $H_{a,k-1}$. +\qed + +\thmn{Lower bound for Contractive Bor\o{u}vka}% +For each $n$ there exists a graph on $\Theta(n)$ vertices and $\Theta(n)$ edges +such that the Contractive Bor\o{u}vka's algorithm spends time $\Omega(n\log n)$ on it. + +\proof +Consider the hedgehog $H_{a,k}$ for $a=\lceil\sqrt n\rceil$ and $k=\lceil\log_2 a\rceil$. +It has $a\cdot 2^k = \Theta(n)$ vertices and ${a \choose 2} + a\cdot 2^k = \Theta(a^2) + \Theta(a^2) = \Theta(n)$ edges +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}$ (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 \endpart