More of the abstract. Reached the end of Chapter 2.

[saga.git] / abstract.tex

\input macros.tex
\finalfalse  %%FIXME

\def\rawchapter#1{\vensure{0.5in}\bigbreak\bigbreak
\leftline{\chapfont #1}
}

\def\rawsection#1{\bigskip
\leftline{\secfont #1}
\nobreak
\medskip
\nobreak
}

\chapter{Introduction}
\bigskip

This thesis tells the story of two well-established problems of algorithmic
graph theory: the minimum spanning trees and ranks of permutations. At distance,
both problems seem to be simple, boring and already solved, because we have poly\-nom\-ial-time
algorithms for them since ages. But when we come closer and seek algorithms that
are really efficient, the problems twirl and twist and withstand many a~brave
attempt at the optimum solution. They also reveal a~vast and diverse landscape
of a~deep and beautiful theory. Still closer, this landscape turns out to be interwoven
with the intricate details of various models of computation and even of arithmetics
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
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.

When compared with the earlier surveys on the minimum spanning trees, most
notably Graham and Hell \cite{graham:msthistory} and Eisner \cite{eisner:tutorial},
this work adds many of the recent advances, the dynamic algorithms and
also the relationship with computational models. No previous work covering
the ranking problems in their entirety is known.

We~have tried to stick to the usual notation except where it was too inconvenient.
Most symbols are defined at the place where they are used for the first time.
To avoid piling up too many symbols at places that speak about a~single fixed graph,
this graph is always called~$G$, its set of vertices and edges are denoted by $V$
and~$E$ respectively, and we~also use~$n$ for the number of its vertices and $m$~for
the number of edges. At places where there could be a~danger of confusion, more explicit notation
is used instead.

\chapter{Minimum Spanning Trees}

\section{The Problem}

The problem of finding a minimum spanning tree of a weighted graph is one of the
best studied problems in the area of combinatorial optimization since its birth.
Its colorful history (see \cite{graham:msthistory} and \cite{nesetril:history} for the full account)
begins in~1926 with the pioneering work of Bor\o{u}vka
\cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
who studied primarily an Euclidean version of the problem related to planning
of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
algorithm for the general version of the problem. As it was well before the dawn of graph
theory, the language of his paper was complicated, so we will better state the problem
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\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)$.
\:A~\df{spanning tree} of~$G$ is any spanning subgraph of~$G$ that is a tree.
\:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
\:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$
  is the smallest possible among all the spanning trees of~$G$.
\:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as
  a union of (minimum) spanning trees of its connected components.
\endlist

Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
mostly geometric setting, and he has discovered another efficient algorithm.
In the next 50 years, several significantly faster algorithms were published, ranging
from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
and Pettie \cite{pettie:ackermann}, to an~algorithm by Pettie \cite{pettie:optimal}
whose time complexity is provably optimal.

Before we discuss the algorithms, let us review the basic properties of spanning trees.
We will mostly follow the theory developed by Tarjan in~\cite{tarjan:dsna} and show
that the weights on edges are not necessary for the definition of the MST.

\defnn{Heavy and light edges}\id{heavy}%
Let~$G$ be a~connected graph with edge weights~$w$ and $T$ its spanning tree. Then:
\itemize\ibull
\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ with~$y$.
\:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
  the edges of this path \df{edges covered by~$e$}.
\:An edge~$e$ is called \df{light with respect to~$T$} (or just \df{$T$-light}) if it covers a~heavier edge, i.e., if there
  is an~edge $f\in T[e]$ such that $w(f) > w(e)$.
\:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge.
\endlist

\thm
A~spanning tree~$T$ is minimum iff there is no $T$-light edge.

\thm
If all edge weights are distinct, then the minimum spanning tree is unique.

\para
When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
its unique minimum spanning tree.
To simplify the description of MST algorithms, we will assume that the weights
of all edges are distinct and that instead of numeric weights we are given a~\df{comparison oracle.}
The oracle is a~function that answers questions of type ``Is $w(e)<w(f)$?'' in
constant time. This will conveniently shield us from problems with representation
of real numbers in algorithms and in the few cases where we need a more concrete
input, we will explicitly state so. In case the weights are not distinct, the ties
can be broken arbitrarily.

\section{Classical algorithms}

The characterization of MST's in terms of light edges makes it easy to develop
the Tarjan's Red-Blue meta-algorithm, which is based on the following properties:

\lemman{Blue lemma, also known as the Cut rule}\id{bluelemma}%
The lightest edge of every cut is contained in the MST.

\lemman{Red lemma, also known as the Cycle rule}\id{redlemma}%
An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.

\para
The algorithm repeatedly colors lightest edges of cuts blue and heaviest
edges of cycles red. We prove that no matter which order of the colorings
we use, the algorithm always stops and the blue edges form the MST.

All three classical MST algorithms (Bor\o{u}vka's, Jarn\'\i{}k's and Kruskal's)
can be then obtained as specializations of this procedure. We also calculate the
time complexity of standard implementations of these algorithms.

\algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst}, and others}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=$ a forest consisting of vertices of~$G$ and no edges.
\:While $T$ is not connected:
\::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
   separating $T_i$ from the rest of~$T$.
\::Add all $e_i$'s to~$T$.
\algout Minimum spanning tree~$T$.
\endalgo

\thm
The Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.

\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 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$.
\algout Minimum spanning tree~$T$.
\endalgo

\thm
The Jarn\'\i{}k's algorithm computes the MST of a~given graph in time $\O(m\log n)$.

\algn{Kruskal \cite{kruskal:mst}}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:Sort edges of~$G$ by their increasing weights.
\:$T\=\hbox{an empty spanning subgraph}$.
\:For all edges $e$ in their sorted order:
\::If $T+e$ is acyclic, add~$e$ to~$T$.
\::Otherwise drop~$e$.
\algout Minimum spanning tree~$T$.
\endalgo

\thm
The Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
If the edges are already sorted by their weights, the time drops to
$\O(m\timesalpha(m,n))$.\foot{Here $\alpha(m,n)$ is the inverse Ackermann's
function.}

\section{Contractive algorithms}

While the classical algorithms are based on growing suitable trees, they
can be also reformulated in terms of edge contraction. Instead of keeping
a~forest of trees, we can keep each tree contracted to a single vertex.
This replaces the relatively complex tree-edge incidencies by simple
vertex-edge incidencies, potentially speeding up the calculation at the
expense of having to perform the contractions.
A~contractive version of the Bor\o{u}vka's algorithm is easy to formulate
and also to analyse:

\algn{Contractive version of Bor\o{u}vka's algorithm}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=\emptyset$.
\:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize edge labels.}
\:While $n(G)>1$:
\::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$.
\::$T\=T\cup \{ \ell(e_1),\ldots,\ell(e_n) \}$.\hfil\break\cmt{Remember labels of all selected edges.}
\::Contract all edges $e_k$, inheriting labels and weights.\foot{In other words, we will ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
\::Flatten $G$ (remove parallel edges and loops).
\algout Minimum spanning tree~$T$.
\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))$.

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.
Given a~planar graph, the algorithm however runs much faster (we get a~linear-time
algorithm much simpler than the one of Matsui \cite{matsui:planar}):

\thm
When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
time $\O(n)$.

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:

\lemma
Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
produced by contracting~$e$ in~$G$, and $\pi$ the bijection between edges of~$G-e$ and
their counterparts in~$G/e$. Then $\mst(G) = \pi^{-1}[\mst(G/e)] + e.$

\chapter{Fine Details of Computation}

\section{Models and machines}

Traditionally, computer scientists have been using a~variety of computational models
as a~formalism in which their algorithms are stated. If we were studying
NP-complete\-ness, we could safely assume that all these models are equivalent,
possibly up to polynomial slowdown which is negligible. In our case, the
differences between good and not-so-good algorithms are on a~much smaller
scale, so we need to state our computation models carefully and develop
a repertoire of basic data structures tailor-made for the fine details of the
models.

In recent decades, most researchers in the area of combinatorial algorithms
have been considering two computational models: the Random Access Machine and the Pointer
Machine. The former is closer to the programmer's view of a~real computer,
the latter is slightly more restricted and ``asymptotically safe.''
We will follow this practice and study our algorithms in both models.

The \df{Random Access Machine (RAM)} is not a~single coherent model, but rather a~family
of closely related machines (See Cook and Reckhow \cite{cook:ram} for one of the usual formal definitions
and Hagerup \cite{hagerup:wordram} for a~thorough description of the differences
between the RAM variants.) We will consider the variant usually called the \df{Word-RAM.}
It allows the ``C-language operators'', i.e., arithmetics and bitwise logical operations,
running in constant time on words of a~specified size.

The \df{Pointer Machine (PM)} also does not seem to have any well established definition.
The various kinds of pointer machines are examined by Ben-Amram in~\cite{benamram:pm},
but unlike the RAM's they turn out to be equivalent up to constant slowdown.
Our formal definition is closely related to the \em{linking automaton} proposed
by Knuth in~\cite{knuth:fundalg}.

\section{Pointer machine techniques}

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)$.
This can be easily handled on both the RAM and the PM by bucket sorting. We develop
a~bunch of pointer-based sorted techniques which can be summarized by the following
lemma:

\lemma
Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are
arbitrary pointers and symbols from a~finite alphabet, to equality classes can
be performed on the Pointer Machine in time $\O(n + \sum_i \vert S_i \vert)$.

\para
A~direct consequence of this unification is a~linear-time algorithm for subtree
isomorphism, significantly simpler than the standard one due to Zemlayachenko (see \cite{zemlay:treeiso}
and also Dinitz et al.~\cite{dinitz:treeiso}). When we apply a~similar technique
to general graphs, we get the framework of topological graph computation
of Buchsbaum et al.~\cite{buchsbaum:verify}.

\defn
A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of
vertices and edges can be arbitrary symbols drawn from a~finite alphabet. The output
of the computation is another labeling of the same graph. This time, the vertices and
edges can be labeled with not only symbols of the alphabet, but also with pointers to the vertices
and edges of the input graph, and possibly also with pointers to outside objects.
A~graph computation is called \df{topological} if it produces isomorphic
outputs for isomorphic inputs. The isomorphism of course has to preserve not only
the structure of the graph, but also the labels in the obvious way.

\defn
For a~collection~$\C$ of graphs, we define $\vert\C\vert$ as the number of graphs in
the collection and $\Vert\C\Vert$ as their total size, i.e., $\Vert\C\Vert = \sum_{G\in\C} n(G) + m(G)$.

\thm
Suppose that we have a~topological graph computation~$\cal T$ that can be performed in time
$T(k)$ for graphs on $k$~vertices. Then we can run~$\cal T$ on a~collection~$\C$
of labeled graphs on~$k$ vertices in time $\O(\Vert\C\Vert + (k+s)^{k(k+2)}\cdot (T(k)+k^2))$,
where~$s$ is a~constant depending only on the number of symbols used as vertex/edge labels.

\section{Data structures on the RAM}

There is a~lot of data structures designed specifically for the RAM. These structures
take advantage of both indexing and arithmetics and they often surpass the known
lower bounds for the same problem on the~PM. In many cases, they achieve constant time
per operation, at least when either the magnitude of the values or the size of
the data structure is suitably bounded.

A~classical result of this type is the tree of van Emde Boas~\cite{boas:vebt}
which represent a~subset of the integers $\{0,\ldots,U-1\}$. It allows insertion,
deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
where $w_{max}$ is the maximum weight.

A~real breakthrough has however been made by Fredman and Willard who introduced
the Fusion trees~\cite{fw:fusion}. They again perform membership and predecessor
operation on a~set of $n$~integers, but with time complexity $\O(\log_W n)$
per operation on a~Word-RAM with $W$-bit words. This of course assumes that
each element of the set fits in a~single word. As $W$ must at least~$\log n$,
the operations take $\O(\log n/\log\log n)$ time and thus we are able to sort $n$~integers
in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and
faster sorting algorithms, culminating with the work of Thorup and Han.
They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort}
and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort},
both in linear space.

The Fusion trees themselves have very limited use in graph algorithms, but the
principles behind them are ubiquitous in many other data structures and these
will serve us well and often. We are going to build the theory of Q-heaps,
which will later lead to a~linear-time MST algorithm for arbitrary integer weights.
Other such structures will help us in building linear-time RAM algorithms for computing the ranks
of various combinatorial structures in Chapter~\ref{rankchap}.

Outside our area, important consequences of RAM data structures include the
Thorup's $\O(m)$ algorithm for single-source shortest paths in undirected
graphs with positive integer weights \cite{thorup:usssp} and his $\O(m\log\log
n)$ algorithm for the same problem in directed graphs \cite{thorup:sssp}. Both
algorithms have been then significantly simplified by Hagerup
\cite{hagerup:sssp}.

Despite the progress in the recent years, the corner-stone of all RAM structures
is still the representation of combinatorial objects by integers introduced by
Fredman and Willard.

First of all, we observe that we can encode vectors in integers:

\notan{Bit strings}\id{bitnota}%
We will work with binary representations of natural numbers by strings over the
alphabet $\{\0,\1\}$: we will use $\(x)$ for the number~$x$ written in binary,
$\(x)_b$ for the same padded to exactly $b$ bits by adding leading zeroes,
and $x[k]$ for the value of the $k$-th bit of~$x$ (with a~numbering of bits such that $2^k[k]=1$).
The usual conventions for operations on strings will be utilized: When $s$
and~$t$ are strings, we write $st$ for their concatenation and
$s^k$ for the string~$s$ repeated $k$~times.
When the meaning is clear from the context,
we will use $x$ and $\(x)$ interchangeably to avoid outbreak of symbols.

\defn
The \df{bitwise encoding} of a~vector ${\bf x}=(x_0,\ldots,x_{d-1})$ of~$b$-bit numbers
is an~integer~$x$ such that $\(x)=\(x_{d-1})_b\0\(x_{d-2})_b\0\ldots\0\(x_0)_b$. In other
words, $x = \sum_i 2^{(b+1)i}\cdot x_i$. (We have interspersed the elements with \df{separator bits.})

\para
If we want to fit the whole vector in a~single machine word, the parameters $b$ and~$d$ must satisfy
the condition $(b+1)d\le W$ (where $W$~is the word size of the machine).
By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
We describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
on their codes. For example, we can handle element-wise comparison of vectors, insertion
in a~sorted vector or shuffling elements of a~vector according to a~fixed permutation,
all in $\O(1)$ time. This also implies that several functions on numbers can be performed
in constant time, most notably binary logarithms.
The vector operations then serve as building blocks for construction of the Q-heaps. We get:

\thm
Let $W$ and~$k$ be positive integers such that $k=\O(W^{1/4})$. Let~$Q$
be a~Q-heap of at most $k$-elements of $W$~bits each. Then we can perform
Q-heap operations on~$Q$ (insertion, deletion, search for a~given value and search
for the $i$-th smallest element) in constant time on a~Word-RAM with word size~$W$,
after spending time $\O(2^{k^4})$ on the same RAM on precomputing of tables.

\cor
For every positive integer~$r$ and $\delta>0$ there exists a~data structure
capable of maintaining the minimum of a~set of at most~$r$ word-sized numbers
under insertions and deletions. Each operation takes $\O(1)$ time on a~Word-RAM
with word size $W=\Omega(r^{\delta})$, after spending time
$\O(2^{r^\delta})$ on precomputing of tables.

\chapter{Ranking Combinatorial Structures}\id{rankchap}%

\chapter{Bibliography}

\dumpbib

\vfill\eject
\ifodd\pageno\else\hbox{}\fi

\bye