\input macros.tex
+\input fonts10.tex
+
\finaltrue
\hwobble=0mm
\advance\hsize by 1cm
\advance\vsize by 20pt
-\font\chapfont=csb17
-\def\rawchapter#1{\vensure{0.5in}\bigbreak\bigbreak
+\def\rawchapter#1{\vensure{0.5in}\bigskip\goodbreak
\leftline{\chapfont #1}
}
-\def\rawsection#1{\bigskip
+\def\rawsection#1{\medskip\smallskip
\leftline{\secfont #1}
\nobreak
\smallskip
\nobreak
}
-\chapter{Introduction}
-\medskip
+\def\schapter#1{\chapter{#1}\medskip}
+
+\schapter{Introduction}
This thesis tells the story of two well-established problems of algorithmic
graph theory: the minimum spanning trees and ranks of permutations. At distance,
itself.
We have tried to cover all known important results on both problems and unite them
-in a~single coherent theory. At many places, we have attempted to contribute my own
+in a~single coherent theory. At many places, we have attempted to contribute our own
little stones to this mosaic: several new results, simplifications of existing
ones, and last, but not least filling in important details where the original
authors have missed some.
\endalgo
\thm
-The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
-time $\O(\min(n^2,m\log n))$.
+The Contractive Bor\o{u}vka's algorithm finds the MST of the graph given as
+its input in time $\O(\min(n^2,m\log n))$.
We also show that this time bound is tight --- we construct an~explicit
family of graphs on which the algorithm spends $\Theta(m\log n)$ steps.
Our formal definition is closely related to the \em{linking automaton} proposed
by Knuth in~\cite{knuth:fundalg}.
-\section{Pointer machine techniques}\id{bucketsort}%
+\section{Bucket sorting and related techniques}\id{bucketsort}%
In the Contractive Bor\o{u}vka's algorithm, we needed to contract a~given
set of edges in the current graph and then flatten the graph, all this in time $\O(m)$.
\section{Minor-closed graph classes}\id{minorclosed}%
The contractive algorithm given in Section~\ref{contalg} has been found to perform
-well on planar graphs, but in the general case its time complexity was not linear.
-Can we find any broader class of graphs where this algorithm is still efficient?
-The right context turns out to be the minor-closed graph classes, which are
+well on planar graphs, but in general its time complexity was not linear.
+Can we find any broader class of graphs where the linear bound holds?
+The right context turns out to be the minor-closed classes, which are
closed under contractions and have bounded density.
\defn\id{minordef}%
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$.
-So we get the following algorithm:
+This leads to the following algorithm:
\algn{Local Bor\o{u}vka's Algorithm, Mare\v{s} \cite{mm:mst}}%
\algo
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 edges of~this forest and iterate.
-
-\algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{itjar}%
-\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^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
-\::While there is a~vertex $v_0\not\in F$:
-\:::Run the Jarn\'\i{}k's algorithm from~$v_0$, stop when:
-\::::all vertices have been processed, or
-\::::a~vertex of~$F$ has been added to the tree, or
-\::::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.}
-\::Contract all edges of~$F$ and flatten~$G$.
-\algout Minimum spanning tree~$T$.
-\endalgo
+contract the edges of~this forest and iterate. This improves the time complexity
+significantly:
\thm\id{itjarthm}%
The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
\algout The minimum spanning forest of~$G$.
\endalgo
-A~careful analysis of this algorithm, based on properties of its recursion tree
+\>A~careful analysis of this algorithm, based on properties of its recursion tree
and on the peak-finding algorithm of the previous section, yields the following time bounds:
\thm
The KKT algorithm runs in time $\O(\min(n^2,m\log n))$ in the worst case on the RAM.
-
-\thm
-The expected time complexity of the KKT algorithm on the RAM is $\O(m)$.
+The expected time complexity is $\O(m)$.
\chapter{Approaching Optimality}\id{optchap}%
their values (the values are however never lowered). This allows for
a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$.
-\defnn{Soft heap interface}%
-The \df{soft heap} contains a~set of distinct items from a~totally ordered universe and it
-supports the following operations:
-\itemize\ibull
-\:$\<Create>(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$.
-\:$\<Insert>(H,x)$ --- Insert a~new item~$x$ into the heap~$H$.
-\:$\<Meld>(P,Q)$ --- Merge two heaps into one, more precisely move all items of a~heap~$Q$
- to the heap~$P$, destroying~$Q$ in the process. Both heaps must have the same~$\varepsilon$.
-\:$\<DeleteMin>(H)$ --- Delete the minimum item of the heap~$H$ and return its value
- (optionally signalling that the value has been corrupted).
-\:$\<Explode>(H)$ --- Destroy the heap and return a~list of all items contained in it
- (again optionally marking those corrupted).
-\endlist
-
-\>In the thesis, we describe the exact mechanics of the soft heaps and analyse its complexity.
+In the thesis, we describe the exact mechanics of the soft heaps and analyse its complexity.
The important properties are characterized by the following theorem:
\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
\section{Robust contractions}
Having the soft heaps at hand, we would like to use them in a~conventional MST
-algorithm in place of a~normal heap. The most efficient specimen of a~heap-based
-algorithm we have seen so far is the Jarn\'\i{}k's algorithm.
-We can try implanting the soft heap in it, preferably in the earlier
-version without Fibonacci heaps as the soft heap lacks the \<Decrease> operation.
+algorithm in place of a~normal heap. We can for example try implanting the soft heap
+in the Jarn\'i{}k's algorithm, preferably in the earlier
+version without Fibonacci heaps as the soft heaps lack the \<Decrease> operation.
This brave, but somewhat simple-minded attempt is however doomed to
fail because of corruption of items inside the soft heap.
While the basic structural properties of MST's no longer hold in corrupted graphs,
\lemman{Generalized contraction}
When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$.
-We can now bring corruption back to the game and state a~``robust'' version
-of this lemma. A~notation for corrupted graphs will be handy:
+Let us bring corruption back to the game and state a~``robust'' version
+of this lemma.
\nota\id{corrnota}%
When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
We recursively compute the MSF of those 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.
+%%The following theorem describes the properties of this partition:
\thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
trees constructed by brute force for very small subgraphs.
-Formally, the decision trees are defined as follows:
+%%Formally, the decision trees are defined as follows:
+Let us define them first:
\defnn{Decision trees and their complexity}\id{decdef}%
A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
problem in all other comparison-based models.
The downside is that we do not know any explicit construction of the optimal
-decision trees, or at least a~non-constructive proof of their complexity.
+decision trees, nor even a~non-constructive proof of their complexity.
On the other hand, the complexity of any existing comparison-based algorithm
can be used as an~upper bound on the decision tree complexity. Also, we can
construct an~optimal decision tree using brute force:
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}).
+\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (see Section \ref{iteralg}).
\:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
\:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
\endalgo
\>Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm})
-and from the proofs of the respective algorithms used as subroutines. As for time complexity:
-
-\lemma\id{optlemma}%
-The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence:
-$$
-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 positive constants and $D$~is the decision tree complexity
-from the previous section.
-
-It turns out that the recurrence is satisfied by the decision tree complexity function
-$D(m,n)$ itself, so we can prove the following theorem by induction:
+and from the proofs of the respective algorithms used as subroutines. As for time complexity, we prove:
\thm
The time complexity of the Optimal algorithm is $\Theta(D(m,n))$.
\problemn{Dynamic connectivity}
Maintain an~undirected graph under a~sequence of the following operations:
\itemize\ibull
-\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
-The structure could support dynamic addition and removal of vertices, too,
-but this is easy to add and infrequently used, so we will rather keep the set
-of vertices fixed for clarity.}
+\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
+(It is possible to modify the structure to support dynamic addition and removal of vertices, too.)
\:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
identifier. This assumes that the edge did not exist yet.
\:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
\:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
\endlist
-In this chapter, we will focus on the dynamic version of the minimum spanning forest.
+\>In this chapter, we will focus on the dynamic version of the minimum spanning forest.
This problem seems to be intimately related to the dynamic connectivity. Indeed, all known
algorithms for dynamic connectivity maintain some sort of a~spanning forest.
This suggests that a~dynamic MSF algorithm could be obtained by modifying the
\paran{Fully dynamic MSF}%
The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
-reduction whose properties are summarized in the following theorem:
+reduction of Holm et al.:
\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
Suppose that we have a~decremental MSF algorithm with the following properties:
comparisons are certainly not sufficient to determine the second best spanning tree. We will
assume that our computation model is able to add, subtract and compare the edge weights
in constant time.
-
Let us focus on finding the second lightest spanning tree first.
\paran{Second lightest spanning tree}%
\lemma
For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find
edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum.
-
-\nota
-We will call this procedure \df{finding the best exchange in $(H,T)$.}
+(We will call this procedure \df{finding the best exchange in $(H,T)$.})
\cor
Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
Once we know~$T_1$ and~$T_2$, how to get~$T_3$? According to the Difference lemma, $T_3$~can be
obtained by a~single exchange from either~$T_1$ or~$T_2$. Therefore we need to find the
best exchange for~$T_2$ and the second best exchange for~$T_1$ and use the better of them.
-The latter is not easy to find directly, but we can get around it:
+The latter is not easy to find directly, so we observe:
\obs\id{tbobs}%
The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
\paran{Invariant edges}%
Our algorithm can be further improved for small values of~$K$ (which seems to be the common
case in most applications) by the reduction of Eppstein \cite{eppstein:ksmallest}.
-We will observe that there are many edges of~$T_1$
+He has proven that there are many edges of~$T_1$
which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
many edges of $G\setminus T_1$ which are excluded from all those spanning trees.
When we combine this with the previous construction, we get the following theorem:
Linear time complexity was reached by Myrvold and Ruskey \cite{myrvold:rank}
for a~non-lexicographic order, which is defined locally by the history of the
-data structure --- in fact, they introduce a linear-time unranking algorithm
-first and then they derive an inverse algorithm without describing the order
-explicitly. However, they leave the problem of lexicographic ranking open.
-
+data structure.
+However, they leave the problem of lexicographic ranking open.
We will describe a~general procedure which, when combined with suitable
RAM data structures, yields a~linear-time algorithm for lexicographic
(un)ranking.
\:Return~$\pi$.
\endalgo
-\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to calculate $L^{-1}(j,[n])$.
+\>We can call $\<Unrank>(j,1,n,[n])$ to calculate $L^{-1}(j,[n])$.
\paran{Representation of sets}%
The most time-consuming parts of the above algorithms are of course operations
rooks on a~hollow chessboard.
\defn
-\itemize\ibull
-\:A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
-\:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares \hbox{$T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$. \hskip-4em} %%HACK
-\endlist
+A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
+A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares \hbox{$T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.}
\obs\id{rooksobs}%
The traces of permutations (and thus the permutations themselves) correspond
For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
-\chapter{Conclusions}
+\schapter{Conclusions}
We have seen the many facets of the minimum spanning tree problem. It has
turned out that while the major question of the existence of a~linear-time
MST algorithm is still open, backing off a~little bit in an~almost arbitrary
direction leads to a~linear solution. This includes classes of graphs with edge
-density at least $\lambda_k(n)$ for an~arbitrary fixed~$k$,
+density at least $\lambda_k(n)$ (the $k$-th row inverse of the Ackermann's function) for an~arbitrary fixed~$k$,
minor-closed classes, and graphs whose edge weights are
integers. Using randomness also helps, as does having the edges pre-sorted.
bucket sorting and the vector computations on the RAM. We hope that they will
be useful in many other algorithms.
-\chapter{Bibliography}
+\schapter{Bibliography}
\dumpbib
projects / saga.git / blobdiff