The right context turns out to be the minor-closed graph classes, which are
closed under contractions and have bounded density.
-\defn
-A~graph~$H$ is a \df{minor} of a~graph~$G$ iff it can be obtained
-from a subgraph of~$G$ by a sequence of simple graph contractions (see \ref{simpcont}).
+\defn\id{minordef}%
+A~graph~$H$ is a \df{minor} of a~graph~$G$ (written as $H\minorof G$) iff it can be obtained
+from a~subgraph of~$G$ by a sequence of simple graph contractions (see \ref{simpcont}).
\defn
A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and
\df{non-trivial} if at least one graph lies in~$\cal C$ and at least one lies outside~$\cal C$.
\example
-Non-trivial minor-closed classes include planar graphs and more generally graphs
-embeddable in any fixed surface. Many nice properties of planar graphs extend
-to these classes, too, most notably the linearity of the number of edges.
+Non-trivial minor-closed classes include:
+\itemize\ibull
+\:planar graphs,
+\:graphs embeddable in any fixed surface (i.e., graphs of bounded genus),
+\:graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles,
+\:graphs of bounded tree-width or path-width.
+\endlist
+
+\para
+Many of the nice structural properties of planar graphs extend to
+minor-closed classes, too (see \cite{diestel:gt} for a~nice overview
+of this theory). The most important property is probably the characterization
+of such classes by forbidden minors.
+
+\defn
+For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class
+of graphs which do not contain any of the graphs in~$\cal H$ as a~minor.
+We will call $\cal H$ the set of \df{forbidden (or excluded) minors} for this class.
+
+\obs
+For every~${\cal H}\ne\emptyset$, the class $\Forb({\cal H})$ is non-trivial
+and closed on minors. This works in the opposite direction as well: for every
+minor-closed class~$\cal C$ there is a~class $\cal H$ such that ${\cal C}=\Forb({\cal H})$.
+One such~$\cal H$ is the complement of~$\cal C$, but smaller sets can be found, too.
+For example, the planar graphs exclude exactly $K_5$ and~$K_{3,3}$ --- this follows
+from the Kuratowski's theorem (the theorem uses forbidden subdivisions, but while
+in general this is not the same as forbidden minors, it is for $K_5$ and $K_{3,3}$).
+The celebrated theorem by Robertson and Seymour guarantees that we can always find
+a~finite set of forbidden minors.
+
+\thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
+For every non-trivial minor-closed graph class~$\cal C$ there exists
+a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$.
+
+\proof
+This theorem has been proven in the series of papers on graph minors
+culminating with~\cite{rs:wagner}. See this paper and follow the references
+to the previous articles in the series.
+\qed
+
+\para
+We will make use of another important property --- the bounded density of minor-closed
+classes. The connection between minors and density dates back to Mader in the 1960's
+and it can be proven without use of the Robertson-Seymour theorem.
\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 $m(G) \le \varrho\cdot n(G)$
holds for every $G\in\cal C$.
-\thmn{Density of minor-closed classes}
-A~minor-closed class of graphs has finite edge density if and only if it is
-a non-trivial class.
+\thmn{Mader \cite{mader:dens}}
+For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
+with average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph.
+
+\proofsketch
+(See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.)
+
+Let us fix~$k$ and prove by induction on~$m$ that every graph with average
+degree $a\ge 2^m$ contains a~subdivision of some graph with $k$~vertices
+and ${k\choose 2}\ge m\ge k$~edges. For $m={k\choose 2}$ the theorem follows
+as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$.
+
+The base case $m=k$: Let us observe that when the average degree
+is~$a$, removing any vertex of degree less than~$a/2$ does not decrease the
+average degree. A~graph with $a\ge 2^k$ therefore has a~subgraph
+with minimum degree $\delta\ge a/2=2^{k-1}$. Such subgraph contains
+a~cycle on more than~$\delta$ vertices, in other words a~subdivision of
+the cycle~$C_k$.
+
+Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and
+assume that the theorem already holds for $m-1$. Without loss of generality,
+$G$~is connected. Consider a~maximal set $U\subseteq V$ such that $G[U]$ is connected
+and the graph $G.U$ ($G$~with $U$~contracted to a~single vertex) has average
+degree at least~$2^m$ (such~$U$ exists, because $G=G.U$ whenever $\vert U\vert=1$).
+Now consider the subgraph~$H$ induced in~$G$ by the
+neighbors of~$U$. Every $v\in V(H)$ must have degree at least~$2^{m-1}$
+(otherwise we can add this vertex to~$U$, contradicting its maximality), so by
+the induction hypothesis $H$ contains a~subdivision of some graph~$R$ with
+$r$~vertices and $m-1$ edges. Any two non-adjacent vertices of~$R$ can be
+connected in the subdivision by a~path lying entirely in~$G[U]$, which reveals
+a~subdivision of a~graph on $m$~vertices. \qed
+
+\thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
+Every non-trivial minor-closed class of graphs has finite edge density.
\proof
-See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions.
+Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$.
+As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(\{K_x\})$, so
+$\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the
+theorem for classes excluding a~single complete graph~$K_x$.
+
+We will show that $\varrho({\cal C})\le 2h(x)$, where $h$~is the function
+from the previous theorem. If any $G\in{\cal C}$ had more than $2h(x)\cdot n(G)$
+edges, its average degree would be at least~$h(x)$, so by the previous theorem
+$G$~would contain a~subdivision of~$K_x$ and therefore $K_x$ as a~minor.
\qed
+\rem
+See also Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions.
+
\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 in this class in time $\O(n)$. (The constant hidden in the~$\O$
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.
+guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
+have degree at most~$t$. Each selected edge removes one such vertex and
+possibly increases the degree of another, so at least $n_i/4$ edges get selected.
+Hence $n_i\le 3/4\cdot n_{i-1}$ and 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 $\delta(v)$ (see the Blue Rule in \ref{rbma}).
\figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
+\rem
+The observation in~Theorem~\ref{mstmcc} was also made by Gustedt in~\cite{gustedt:parallel},
+who studied a~parallel version of the contractive Bor\o{u}vka's algorithm applied
+to minor-closed classes.
+
%--------------------------------------------------------------------------------
\section{Using Fibonacci heaps}
\id{fibonacci}
-We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\O(m\log n)$ time
-(and this bound can be easily shown to be tight). Fredman and Tarjan have shown a~faster
-implementation in~\cite{ft:fibonacci} using their Fibonacci heaps. In this section,
-we convey their results and we show several interesting consequences.
+We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
+Fredman and Tarjan have shown a~faster implementation in~\cite{ft:fibonacci}
+using their Fibonacci heaps. In this section, we convey their results and we
+show several interesting consequences.
-The previous implementation of the algorithm used a binary heap to store all neighboring
-edges of the cut~$\delta(T)$. Instead of that, we will remember the vertices adjacent
-to~$T$ and for each such vertex~$v$ we will keep the lightest edge~$uv$ such that $u$~lies
-in~$T$. We will call these edges \df{active edges} and keep them in a~heap, ordered by weight.
+The previous implementation of the algorithm used a binary heap to store all edges
+separating the current tree~$T$ from the rest of the graph, i.e., edges of the cut~$\delta(T)$.
+Instead of that, we will remember the vertices adjacent to~$T$ and for each such vertex~$v$ we
+will maintain the lightest edge~$uv$ such that $u$~lies in~$T$. We will call these edges \df{active edges}
+and keep them in a~Fibonacci heap, ordered by weight.
When we want to extend~$T$ by the lightest edge of~$\delta(T)$, it is sufficient to
-find the lightest active edge~$uv$ and add this edge to~$T$ together with a new vertex~$v$.
+find the lightest active edge~$uv$ and add this edge to~$T$ together with the new vertex~$v$.
Then we have to update the active edges as follows. The edge~$uv$ has just ceased to
be active. We scan all neighbors~$w$ of the vertex~$v$. When $w$~is in~$T$, no action
is needed. If $w$~is outside~$T$ and it was not adjacent to~$T$ (there is no active edge
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{Active Edge Jarn\'\i{}k; 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$.
\:$T\=$ a tree containing just the vertex~$v_0$.
-\:$H\=$ a~heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(vw)$, initially empty.
-\:$A\=$ an~auxiliary array mapping vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
+\:$H\=$ a~Fibonacci heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(uv)$, initially empty.
+\:$A\=$ a~mapping of vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
\:\<Insert> all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly.
\:While $H$ is not empty:
\::$(u,v)\=\<DeleteMin>(H)$.
\algout Minimum spanning tree~$T$.
\endalgo
+\para
+To analyze the time complexity of this algorithm, we will use the standard
+theorem on~complexity of the Fibonacci heap:
+
\thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations
with the indicated amortized time complexities:
\itemize\ibull
\:\<DeleteMin> (deletion of the minimal element) in $\O(\log n)$,
\:\<Delete> (deletion of an~arbitrary element) in $\O(\log n)$,
\endlist
-\>where $n$ is the maximum number of elements present in the heap at the time of
+\>where $n$ is the number of elements present in the heap at the time of
the operation.
\proof
\qed
\thm
-Algorithm~\ref{jarniktwo} with a~Fibonacci heap finds the MST of the input graph in time~$\O(m+n\log n)$.
+Algorithm~\ref{jarniktwo} with the Fibonacci heap finds the MST of the input graph in time~$\O(m+n\log n)$.
\proof
The algorithm always stops, because every edge enters the heap~$H$ at most once.
The time complexity is $\O(m)$ plus the cost of the heap operations. The algorithm
performs at most one \<Insert> or \<Decrease> per edge and exactly one \<DeleteMin>
-per vertex and there are at most $n$ elements in the heap at any given time,
-so by the previous theorem the operations take $\O(m+n\log n)$ time in total.
+per vertex. There are at most $n$ elements in the heap at any given time,
+thus by the previous theorem the operations take $\O(m+n\log n)$ time in total.
\qed
\cor
in the form of a~complete $d$-regular tree. \<Insert>, \<Decrease> and other operations
involving bubbling the values up spend $\O(1)$ time at a~single level, so they run
in~$\O(\log_d n)$ time. \<Delete> and \<DeleteMin> require bubbling down, which incurs
-comparison with all~$d$ sons at every level, so they run in~$\O(d\log_d n)$.
+comparison with all~$d$ sons at every level, so they spend $\O(d\log_d n)$.
With this structure, the time complexity of the whole algorithm
-is $\O(nd\log_d n + m\log_d n)$, which suggests setting $d=m/n$, giving $\O(m\log_{m/n}n)$.
+is $\O(nd\log_d n + m\log_d n)$, which suggests setting $d=m/n$, yielding $\O(m\log_{m/n}n)$.
This is still linear for graphs with density at~least~$n^{1+\varepsilon}$.
Another possibility is to use the 2-3-heaps \cite{takaoka:twothree} or Trinomial
heaps \cite{takaoka:trinomial}. Both have the same asymptotic complexity as Fibonacci
-heaps (the latter even in worst case, but it does not matter here) and their
-authors claim implementation advantages.
+heaps (the latter even in the worst case, but it does not matter here) and their
+authors claim faster implementation.
\FIXME{Mention Thorup's Fibonacci-like heaps for integers?}
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.
+MST by the Active Edge 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
+\:Run the Active Edge Jarn\'\i{}k's algorithm (\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$.
\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
+Active Edge Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while.
+A~good choice of the stopping condition is to place a~limit on the size of the heap.
+We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
+we 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.
\:$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 heap size}
+\::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on 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:
+\:::Run the Active Edge 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.
+\::::the heap has grown to 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.}
\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
+phase by~$G_i$ and likewise with the other parameters. Let the trees from which
+$F_i$~has been constructed 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
\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$ \<DeleteMin>'s over the course of the phase.
+are edge-disjoint, so there are at most~$n_i$ \<DeleteMin>'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+m) = \O(m)$.
\qed
\proof
As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient
-to establish that there are at least~$t_i$ edges incident with the vertices of every
-such tree~(*).
+to establish that there are at least~$t_i$ edges incident with every such tree, including
+connecting two vertices of the tree.
The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the 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 heap had more than~$t_i$ elements (step~10): since the each elements stored in the heap
+ corresponds to a~unique edges incident with~$R_i^j$, we have enough such edges;
\: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.}
+ This is the place where we needed to count the interior edges as well.}
\:all vertices have been processed (step~8): this can happen only in the final phase.
\qeditem
\endlist
\thm\id{itjarthm}%
The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
-$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n < m/n \}$.
+$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n \le m/n \}$.
\proof
Phases are finite and in every phase at least one edge is contracted, so the outer
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
+Let us bound the sizes of the graphs processed in the 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}$,
+2m_i/t_i$. Then $t_{i+1} = 2^{\lceil 2m/n_{i+1} \rceil} \ge 2^{2m/n_{i+1}} \ge 2^{2m/(2m_i/t_i)} = 2^{(m/m_i)\cdot t_i} \ge 2^{t_i}$,
therefore:
$$
-\left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\vdots^{\scriptstyle m/n}}}} $}}\;\right\}
+\left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\rddots^{\scriptstyle m/n}}}} $}}\;\right\}
\,\hbox{a~tower of~$i$ exponentials.}
$$
As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time
%--------------------------------------------------------------------------------
-\section{Verification of minimality}
+%\section{Verification of minimality}
\endpart
projects / saga.git / blobdiff