Abstract: added Conclusions and reviewed chapters 1--5.

[saga.git] / abstract.tex

\input macros.tex
\finaltrue
\hwobble=0mm
\advance\hsize by 1cm
\advance\vsize by 20pt

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

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

\chapter{Introduction}
\medskip

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.

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, perform a~\df{Bor\o{u}vka step:}
\::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 the graph given as input in time $\O(m\log n)$.
If the edges are already sorted by their weights, the time drops to
$\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's
function.

\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
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}\id{contbor}%
\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) \}$.\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:

\lemman{Contraction lemma}\id{contlemma}%
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 the following two computational models, and we will do likewise.

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}\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)$.
This can be easily handled on both the RAM and the PM by bucket sorting. We develop
a~bunch of pointer-based sorting 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}\id{ramds}%

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 represents 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 further improved by Han and Thorup \cite{han:detsort,hanthor:randsort}.

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{Advanced MST Algorithms}

\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
closed under contractions and have bounded density.

\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.

\defn
A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and
every minor~$H$ of~$G$, the graph~$H$ lies in~$\cal C$ as well. A~class~$\cal C$ is called
\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,
graphs embeddable in any fixed surface (i.e., graphs of bounded genus),
graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles,
and graphs of bounded tree-width or path-width.

\para
Many of the nice structural properties of planar graphs extend to
minor-closed classes, too (see Lov\'asz \cite{lovasz:minors} for a~nice survey
of this theory and Diestel \cite{diestel:gt} for some of the deeper results).
For analysis of the contractive algorithm, we will make use of the bounded
density of minor-closed classes:

\defn\id{density}%
Let $G$ be a~graph and $\cal C$ be a class of graphs. We define the \df{edge density}
$\varrho(G)$ of~$G$ as the average number of edges per vertex, i.e., $m(G)/n(G)$. The
edge density $\varrho(\cal C)$ of the class is then defined as the infimum of $\varrho(G)$ over all $G\in\cal C$.

\thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
Every non-trivial minor-closed class of graphs has finite edge density.

\thmn{MST on minor-closed classes, Mare\v{s} \cite{mm:mst}}\id{mstmcc}%
For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
algorithm (\ref{contbor}) finds the MST of any graph of this class in time
$\O(n)$. (The constant hidden in the~$\O$ depends on the class.)

\paran{Local contractions}\id{nobatch}%
The contractive algorithm uses ``batch processing'' to perform many contractions
in a single step. It is also possible to perform them one edge at a~time,
batching only the flattenings. A~contraction of an edge~$uv$ can be done in time~$\O(\deg(u))$,
so we have to make sure that there is a~steady supply of low-degree vertices.
It indeed is 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$.

So we get the following algorithm:

\algn{Local Bor\o{u}vka's Algorithm, Mare\v{s} \cite{mm:mst}}%
\algo
\algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
\:$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~$e$.
\:::$T\=T + \ell(e)$.
\::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.)

\section{Iterated algorithms}\id{iteralg}%

We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
Fredman and Tarjan \cite{ft:fibonacci} have shown a~faster implementation using their Fibonacci
heaps, which runs in time $\O(m+n\log n)$. This is $\O(m)$ whenever the density of the
input graph reaches $\Omega(\log n)$. This suggests that we could combine the algorithm with
another MST algorithm, which identifies a~subset of the MST edges and contracts
them to increase the density of the graph. For example, if we perform several Bor\o{u}vka
steps and then we run the Jarn\'\i{}k's algorithm, we find the MST in time $\O(m\log\log n)$.

Actually, there is a~much better choice of the algorithms to combine: use the
Jarn\'\i{}k's algorithm with a~Fibonacci heap multiple times, each time stopping it 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 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

\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 \mid \log^{(i)}n \le m/n \}$.

\cor
The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.

\paran{Integer weights}%
The algorithm spends most of the time in phases which have small heaps. Once the
heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
to guarantee that at most~$k$ phases remain. This means that if we are able to
construct a~heap of size $\Omega(\log^{(k)} n)$ with constant time per operation,
we can get a~linear-time algorithm for MST. This is the case when the weights are
integers (we can use the Q-heap trees from Section~\ref{ramds}).

\thmn{MST for integer weights, Fredman and Willard \cite{fw:transdich}}\id{intmst}%
MST of a~graph with integer edge weights can be found in time $\O(m)$ on the Word-RAM.

\section{Verification of minimality}\id{verifysect}%

Now we will turn our attention to a~slightly different problem: given a~spanning
tree, how to verify that it is minimum? We will show that this can be achieved
in linear time and it will serve as a~basis for a~randomized linear-time
MST algorithm in the next section.

MST verification has been studied by Koml\'os \cite{komlos:verify}, who has
proven that $\O(m)$ edge comparisons are sufficient, but his algorithm needed
super-linear time to find the edges to compare. Dixon, Rauch and Tarjan \cite{dixon:verify}
have later shown that the overhead can be reduced
to linear time on the RAM using preprocessing and table lookup on small
subtrees. Later, King has given a~simpler algorithm in \cite{king:verifytwo}.

To verify that a~spanning tree~$T$ is minimum, it is sufficient to check that all
edges outside~$T$ are $T$-heavy. For each edge $uv\in E\setminus T$, we will
find the heaviest edge of the tree path $T[u,v]$ (we will call it the \df{peak}
of the path) and compare its weight to $w(uv)$. We have therefore transformed
the MST verification to the problem of finding peaks for a~set of \df{query
paths} on a~given tree. By a~sequence of further transformations, we can even
assume that the given tree is \df{complete branching} (all vertices are on
the same level and internal vertices always have outdegree~2) and that the
query paths join a~vertex with one of its ancestors.

Koml\'os has given a~simple algorithm that traverses the complete branching
tree recursively. At each moment, it maintains an~array of peaks of the restrictions
of the query paths to the subtree below the current vertex. If we account for the
comparisons performed by this algorithm carefully and express the bound in terms
of the size of the original problem (before all the transformations), we get:

\thmn{Verification of the MST, Koml\'os \cite{komlos:verify}}\id{verify}%
For every weighted graph~$G$ and its spanning tree~$T$, it is sufficient to
perform $\O(m)$ comparisons of edge weights to determine whether~$T$ is minimum
and to find all $T$-light edges in~$G$.

It remains to demonstrate that the overhead of the algorithm needed to find
the required comparisons and to infer the peaks from their results can be decreased,
so that it gets bounded by the number of comparisons and therefore also by $\O(m)$.
We will follow the idea of King from \cite{king:verifytwo}, but as we have the power
of the RAM data structures from Section~\ref{ramds} at our command, the low-level
details will be easier. Still, the construction is rather technical, so we omit
it from this abstract and state only the final theorem:

\thmn{Verification of MST on the RAM}\id{ramverify}%
There is a~RAM algorithm which for every weighted graph~$G$ and its spanning tree~$T$
determines whether~$T$ is minimum and finds all $T$-light edges in~$G$ in time $\O(m)$.

\section{A randomized algorithm}\id{randmst}%

When we analysed the Contractive Bor\o{u}vka's algorithm in Section~\ref{contalg},
we observed that while the number of vertices per iteration decreases exponentially,
the number of edges generally does not, so we spend $\Theta(m)$ time on every phase.
Karger, Klein and Tarjan \cite{karger:randomized} have overcome this problem by
combining the Bor\o{u}vka's algorithm with filtering based on random sampling.
This leads to a~randomized algorithm which runs in linear expected time.

The principle of the filtering is simple: Let us consider any spanning tree~$T$
of the input graph~$G$. Each edge of~$G$ that is $T$-heavy is the heaviest edge
of some cycle, so by the Red lemma it cannot participate in
the MST of~$G$. We can therefore discard all $T$-heavy edges and continue with
finding the MST on the reduced graph. Of course, not all choices of~$T$ are equally
good, but it will soon turn out that when we take~$T$ as the MST of a~randomly selected
subgraph, only a~small expected number of edges remains:

\lemman{Random sampling, Karger \cite{karger:sampling}}\id{samplemma}%
Let $H$~be a~subgraph of~$G$ obtained by including each edge independently
with probability~$p$. Let further $F$~be the minimum spanning forest of~$H$. Then the
expected number of $F$-nonheavy\foot{That is, $F$-light edges and also edges of~$F$ itself.}
edges in~$G$ is at most $n/p$.

\para
We will formulate the algorithm as a~doubly-recursive procedure. It alternatively
performs steps of the Bor\o{u}vka's algorithm and filtering based on the above lemma.
The first recursive call computes the MSF of the sampled subgraph, the second one
finds the MSF of the original graph, but without the heavy edges.

\algn{MSF by random sampling --- the KKT algorithm}\id{kkt}%
\algo
\algin A~graph $G$ with an~edge comparison oracle.
\:Remove isolated vertices from~$G$. If no vertices remain, stop and return an~empty forest.
\:Perform two Bor\o{u}vka steps (iterations of Algorithm \ref{contbor}) on~$G$ and
  remember the set~$B$ of the edges having been contracted.
\:Select a~subgraph~$H\subseteq G$ by including each edge independently with
  probability $1/2$.
\:$F\=\msf(H)$ calculated recursively.
\:Construct $G'\subseteq G$ by removing all $F$-heavy edges of~$G$.
\:$R\=\msf(G')$ calculated recursively.
\:Return $R\cup B$.
\algout The minimum spanning forest of~$G$.
\endalgo

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)$.

\chapter{Approaching Optimality}\id{optchap}%

\section{Soft heaps}\id{shsect}%

A~vast majority of MST algorithms that we have encountered so far is based on
the Tarjan's Blue rule (Lemma \ref{bluelemma}), the only exception being the
randomized KKT algorithm, which also used the Red rule (Lemma \ref{redlemma}). Recently, Chazelle
\cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann} have presented new
deterministic algorithms for the MST which are also based on the combination of
both rules. They have reached worst-case time complexity
$\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to
their results and especially to another algorithm by Pettie and Ramachandran
\cite{pettie:optimal} which is provably optimal.

At the very heart of all these algorithms lies the \df{soft heap} discovered by
Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
the expense of \df{corrupting} a~fraction of the inserted elements by raising
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.
The important properties are characterized by the following theorem:

\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
heap contains at most $\varepsilon n$ corrupted items.

\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.
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,
there is a~weaker form of the Contraction lemma that takes the corrupted edges into account.
Before we prove this lemma, we expand our awareness of subgraphs which can be contracted.

\defn
A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,
of~$G$'s edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints
of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.

For example, when we stop the Jarn\'\i{}k's algorithm at some moment and
we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.
We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
of contractible subgraphs:

\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:

\nota\id{corrnota}%
When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of
some of the edges in~$R$.
Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with
exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$).

\lemman{Robust contraction, Chazelle \cite{chazelle:almostacker}}\id{robcont}%
Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.

\para
We will now mimic the Iterated Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
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.

\thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
and~$t$, we can construct a~collection $\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that:

\numlist\ndotted
\:All the clusters and the set~$R^\C$ are mutually edge-disjoint.
\:Each cluster contains at most~$t$ vertices.
\:Each vertex of~$G$ is contained in at least one cluster.
\:The connected components of the union of all clusters have at least~$t$ vertices each,
  except perhaps for those which are equal to a~connected component of $G\setminus R^\C$.
\:$\vert R^\C\vert \le 2\varepsilon m$.
\:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
\:The construction takes $\O(n+m\log (1/\varepsilon))$ time.
\endlist

\section{Decision trees}\id{dtsect}%

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:

\defnn{Decision trees and their complexity}\id{decdef}%
A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
are labeled with pairs of $G$'s edges to be compared, each of the two outgoing tree edges
corresponds to one possible result of the comparison.
Leaves of the tree are labeled with spanning trees of the graph~$G$.

A~\df{computation} of the decision tree on a~specific permutation of edge weights
in~$G$ is the path from the root to a~leaf such that the outcome of every comparison
agrees with the edge weights. The result of the computation is the spanning tree
assigned to its final leaf.
A~decision tree is \df{correct} iff for every permutation the corresponding
computation results in the real MSF of~$G$ with the particular weights.

The \df{time complexity} of a~decision tree is defined as its depth. It therefore
bounds the number of comparisons spent on every path. (It need not be equal since
some paths need not correspond to an~actual computation --- the sequence of outcomes
on the path could be unsatisfiable.)

A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
among the correct decision trees for the given graph.
We will denote an~arbitrary optimal decision tree for~$G$ by~${\cal D}(G)$ and its
complexity by~$D(G)$.

The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~$D(G)$
over all graphs~$G$ with $n$~vertices and~$m$ edges.

\obs
Decision trees are the most general deterministic comparison-based computation model possible.
The only operations that count in its time complexity are comparisons. All
other computation is free, including solving NP-complete problems or having
access to an~unlimited source of non-uniform constants. The decision tree
complexity is therefore an~obvious lower bound on the time complexity of the
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.
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:

\lemma
An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
the Pointer Machine in time $\O(2^{2^{4n^2}})$.

\section{An optimal algorithm}\id{optalgsect}%

Once we have developed the soft heaps, partitioning and MST decision trees,
it is now simple to state the Pettie's and Ramachandran's MST algorithm
and prove that it is asymptotically optimal among all MST algorithms in
comparison-based models. Several standard MST algorithms from the previous
chapters will also play their roles.
We will describe the algorithm as a~recursive procedure:

\algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
\algo
\algin A~connected graph~$G$ with an~edge comparison oracle.
\:If $G$ has no edges, return an~empty tree.
\:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}
\:Call the partitioning procedure (\ref{partthm}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
  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}).
\:$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.
\:$F_C \= \mst(G_C)$ obtained by a~recursive call to this algorithm.
\:Return $F_B \cup F_C$.
\algout The minimum spanning tree of~$G$.
\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:

\thm
The time complexity of the Optimal algorithm is $\Theta(D(m,n))$.

\paran{Complexity of MST}%
As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem
is still open and so therefore is the time complexity of the optimal algorithm. However,
every time we come up with another comparison-based algorithm, we can use its complexity
(or more specifically the number of comparisons it performs, which can be even lower)
as an~upper bound on the optimal algorithm.
The best explicit comparison-based algorithm known to date has been discovered by Chazelle
\cite{chazelle:ackermann} and independently by Pettie \cite{pettie:ackermann}. It achieves complexity $\O(m\timesalpha(m,n))$.
Using any of these results, we can prove an~Ackermannian upper bound on the
optimal algorithm:

\thm
The time complexity of the Optimal algorithm is $\O(m\timesalpha(m,n))$.

\chapter{Dynamic Spanning Trees}\id{dynchap}%

\section{Dynamic graph algorithms}

In many applications, we often need to solve a~certain graph problem for a~sequence of graphs that
differ only a~little, so recomputing the solution for every graph from scratch would be a~waste of
time. In such cases, we usually turn our attention to \df{dynamic graph algorithms.} A~dynamic
algorithm is in fact a~data structure that remembers a~graph. It offers operations that modify the
structure of the graph and also operations that query the result of the problem for the current
state of the graph. A~typical example of a~problem of this kind is dynamic maintenance of connected
components:

\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.}
\:$\<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.
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
mechanics of the data structure to keep the forest minimum.
We however have to answer one important question first: What should be the output of
our MSF data structure? Adding an~operation that returns the MSF of the current
graph would be of course possible, but somewhat impractical as this operation would have to
spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
be making the \<Insert> and \<Delete> operations report the list of modifications
of the MSF implied by the change in the graph. It is easy to prove that $\O(1)$
modifications always suffice, so we can formulate our problem as follows:

\problemn{Dynamic minimum spanning forest}
Maintain an~undirected graph with distinct weights on edges (drawn from a~totally ordered set)
and its minimum spanning forest under a~sequence of the following operations:
\itemize\ibull
\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
\:$\<Insert>(G,u,v,w)$ --- Insert an~edge $uv$ of weight~$w$ to~$G$. Return its unique
        identifier and the list of additions and deletions of edges in $\msf(G)$.
\:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
        Return the list of additions and deletions of edges in $\msf(G)$.
\endlist

\paran{Incremental MSF}%
In case only edge insertions are allowed, the problem reduces to finding the heaviest
edge (peak) on the tree path covered by the newly inserted edge and replacing the peak
if needed. This can be handled quite efficiently by using the Link-Cut trees of Sleator
and Tarjan \cite{sleator:trees}. We obtain logarithmic time bound:

\thmn{Incremental MSF}
When only edge insertions are allowed, the dynamic MSF can be maintained in time $\O(\log n)$
amortized per operation.

\section{Dynamic connectivity}

The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and
$\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.

The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
replacement among the non-tree edges.

To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
We will maintain the following \em{invariants:}

{\narrower
\def\iinv{{\bo I\the\itemcount~}}
\numlist\iinv
\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
(This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
anyway.)
\endlist
}

At the beginning, the graph contains no edges, so both invariants are trivially
satisfied. Newly inserted edges enter level~0, which cannot break I1 nor~I2.

When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
smaller one. We will try to find the replacement edge of the highest possible
level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According
to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can move all level~$\ell$
edges of~$T_1$ to level~$\ell+1$ without violating either invariant.

We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
will be the grist for the mill of our amortization argument: We can charge most of the work on level
increases and we know that the level of each edge can reach at most~$L$.)

If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
lower level and so on. If there is no replacement edge at level~0, the tree~$T$
remains disconnected.

The implementation uses the Eulerian Tour trees of Henzinger and King \cite{henzinger:randdyn}
to represent the forests~$F_\ell$ together with the non-tree edges at each particular level.
A~simple amortized analysis using the levels yields the following result:

\thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per
\<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
in the worst case.

\rem\id{dclower}%
An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity
problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell
probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm
\cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and
$\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims
that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations,
so it does not fit the definition of the PM we use. The algorithm only does not
need direct indexing of arrays.) So far, it is not known how to extend this algorithm
to fit our needs, so we omit the details.

\section{Dynamic spanning forests}\id{dynmstsect}%

Let us turn our attention back to the dynamic MSF.
Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved
the decremental version of the problem first (which starts with a~given graph and only edge deletions
are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.

\paran{Decremental MSF}%
Turning the algorithm from the previous section to the decremental MSF requires only two
changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
the lightest possible choice. We will therefore use a~weighted version of the ET-trees.
We must ensure that the lower levels cannot contain a~lighter replacement edge,
but fortunately the light edges tend to ``bubble up'' in the hierarchy of
levels. This can be formalized in form of the following invariant:

{\narrower
\def\iinv{{\bo I\the\itemcount~}}
\numlist\iinv
\itemcount=2
\:On every cycle, the heaviest edge has the smallest level.
\endlist
}

\>This immediately implies that we always select the right replacement edge:

\lemma\id{msfrepl}%
Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
edges for~$e$, the lightest one is at the maximum level.

A~brief analysis also shows that the invariant I3 is observed by all operations
on the structure. We can conclude:

\thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of
edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then
updated in time $\O(\log^2 n)$ amortized per operation.

\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:

\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
Suppose that we have a~decremental MSF algorithm with the following properties:
\numlist\ndotted
\:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
\:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
\endlist
\>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
with no edges, that performs $m$~insertions and deletions in amortized time:
$$
\O\left( \log^3 n + \sum_{i=1}^{\log m} \sum_{j=1}^i \; t(\min(n,2^j), 2^j) \right) \hbox{\quad per operation.}
$$

\corn{Fully dynamic MSF}\id{dynmsfcorr}%
There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized
per operation for graphs on $n$~vertices.

\paran{Dynamic MSF with limited edge weights}%
If the set from which the edge weights are drawn is small, we can take a~different
approach. If only two values are allowed, we split the graph to subgraphs $G_1$ and~$G_2$
induced by the edges of the respective weights and we maintain separate connectivity
structures (together with a~spanning tree) for $G_1$ and $G_2 \cup T_1$ (where $T_1$
is a~spanning tree of~$G_1$). We can easily modify the structure for $G_2\cup
T_1$ to prefer the edges of~$T_1$. This ensures that the spanning tree of $G_2\cup T_1$
will be the MST of the whole~$G$.

If there are more possible values, we simply iterate this construction: the $i$-th
structure contains edges of weight~$i$ and the edges of the spanning tree from the
$(i-1)$-th structure. We get:

\thmn{MSF with limited edge weights}
There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.

\section{Almost minimum trees}\id{kbestsect}%

In some situations, finding the single minimum spanning tree is not enough and we are interested
in the $K$~lightest spanning trees, usually for some small value of~$K$. Katoh, Ibaraki
and Mine \cite{katoh:kmin} have given an~algorithm of time complexity $\O(m\log\beta(m,n) + Km)$,
building on the MST algorithm of Gabow et al.~\cite{gabow:mst}.
Subsequently, Eppstein \cite{eppstein:ksmallest} has discovered an~elegant preprocessing step which allows to reduce
the running time to $\O(m\log\beta(m,n) + \min(K^2,Km))$ by eliminating edges
which are either present in all $K$ trees or in none of them.
We will show a~variant of their algorithm based on the MST verification
procedure of Section~\ref{verifysect}.

In this section, we will require the edge weights to be numeric, because
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}%
Suppose that we have a~weighted graph~$G$ and a~sequence $T_1,\ldots,T_z$ of all its spanning
trees. Also suppose that the weights of these spanning trees are distinct and that the sequence
is ordered by weight, i.e., $w(T_1) < \ldots < w(T_z)$ and $T_1 = \mst(G)$. Let us observe
that each tree is similar to at least one of its predecessors:

\lemman{Difference lemma}\id{kbl}%
For each $i>1$ there exists $j<i$ such that $T_i$ and~$T_j$ differ by a~single edge exchange.

\para
This lemma implies that the second best spanning tree~$T_2$ differs from~$T_1$ by a~single
edge exchange. It remains to find which exchange it is, but this can be reduced to finding
peaks of the paths covered by the edges outside~$T_1$, which we already are able to solve
efficiently by the methods of Section~\ref{verifysect}. Therefore:

\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)$.}

\cor
Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.

\paran{Third lightest spanning tree}%
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:

\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)$:

\itemize\ibull
\:If $T_3 = T_1-e'+f'$ for $e'\ne e$, then $T_3/e = (T_1/e)-e'+f'$ in~$G_1$.
\:If $T_3 = T_1-e+f'$, then $T_3 = T_2 - f + f'$ in~$G_2$.
\:If $T_3 = T_2-e'+f'$, then this exchange is found in~$G_2$.
\endlist

\>Thus we can run the previous algorithm for finding the best edge exchange
on both~$G_1$ and~$G_2$ and find~$T_3$ again in time $\O(m)$.

\paran{Further spanning trees}%
The construction of auxiliary graphs can be iterated to obtain $T_1,\ldots,T_K$
for an~arbitrary~$K$. We will build a~\df{meta-tree} of auxiliary graphs. Each node of this meta-tree
carries a~graph and its minimum spanning tree. The root node contains~$(G,T_1)$,
its sons have $(G_1,T_1/e)$ and $(G_2,T_2)$. When $T_3$ is obtained by an~exchange
in one of these sons, we attach two new leaves to that son and we let them carry the two auxiliary
graphs derived by contracting or deleting the exchanged edge. Then we find the best
edge exchanges among all leaves of the new meta-tree and repeat the process. By Observation \ref{tbobs},
each spanning tree of~$G$ is generated exactly once. The Difference lemma guarantees that
the trees are enumerated in the increasing order. So we get:

\lemma\id{kbestl}%
Given~$G$ and~$T_1$, we can find $T_2,\ldots,T_K$ in time $\O(Km + K\log K)$.

\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$
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:

\thmn{Finding $K$ lightest spanning trees}\id{kbestthm}%
For a~given graph~$G$ with real edge weights and a~positive integer~$K$, the $K$~best spanning trees can be found
in time $\O(m\timesalpha(m,n) + \min(K^2,Km + K\log K))$.

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

\section{Ranking and unranking}\id{ranksect}%

The techniques for building efficient data structures on the RAM, which we have described
in Section~\ref{ramds}, can be also used for a~variety of problems related
to ranking of combinatorial structures. Generally, the problems are stated
in the following way:

\defn\id{rankdef}%
Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
$R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ ordered by~$\prec$
and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function} for $C$ and~$\prec$. When the set
and the order are clear from the context, we will use plain~$R(x)$ and $R^{-1}(x)$.
Also, when $\prec$ is defined on a~superset~$C'$ of~$C$, we naturally extend $R_C(x)$
to elements $x\in C'\setminus C$.

\example
Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered
lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that
is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the
notation of Section~\ref{ramds}). Obviously, $R(x)$ is the integer whose binary
representation is the string~$x$.

%--------------------------------------------------------------------------------

\section{Ranking of permutations}
\id{pranksect}

One of the most common ranking problems is ranking of permutations on the set~$[n]=\{1,2,\ldots,n\}$.
This is frequently used to create arrays indexed by permutations: for example in Ruskey's algorithm
for finding Hamilton cycles in Cayley graphs (see~\cite{ruskey:ham} and \cite{ruskey:hce})
or when exploring state spaces of combinatorial puzzles like the Loyd's Fifteen \cite{ss:fifteen}.
Many other applications are surveyed by Critani et al.~\cite{critani:rau} and in
most cases, the time complexity of the whole algorithm is limited by the efficiency
of the (un)ranking functions.

The permutations are usually ranked according to their lexicographic order.
In fact, an~arbitrary order is often sufficient if the ranks are used solely
for indexing of arrays. The lexicographic order however has an~additional advantage
of a~nice structure, which allows various operations on permutations to be
performed directly on their ranks.

Na\"\i{}ve algorithms for lexicographic ranking require time $\Theta(n^2)$ in the
worst case \cite{reingold:catp} and even on average~\cite{liehe:raulow}.
This can be easily improved to $O(n\log n)$ by using either a binary search
tree to calculate inversions, or by a divide-and-conquer technique, or by clever
use of modular arithmetic (all three algorithms are described in Knuth
\cite{knuth:sas}). Myrvold and Ruskey \cite{myrvold:rank} mention further
improvements to $O(n\log n/\log \log n)$ by using the RAM data structures of Dietz
\cite{dietz:oal}.

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.

We will describe a~general procedure which, when combined with suitable
RAM data structures, yields a~linear-time algorithm for lexicographic
(un)ranking.

\nota\id{brackets}%
We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
(in other words, arrays) containing every element of~$A$ exactly once. We will
use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$,
and sub-tuples: $\pi[i\ldots j] = (\pi[i],\pi[i+1],\ldots,\pi[j])$.
The lexicographic ranking and unranking functions for the permutations on~$A$
will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively.

\obs\id{permrec}%
Let us first observe that permutations have a simple recursive structure.
If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, the
elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots n]$.
Moreover, when we fix $\pi[1]$, all permutations on the smaller set occur exactly
once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
$\pi[2\ldots n]$.

This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)rank\-ing
of permutations on a $(n-1)$-element set, which suggests a straightforward
algorithm, but unfortunately this set is different from $[n-1]$ and it even
depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
but it would require linear time per iteration. To avoid this, we generalize the
problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set
$A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula:
$$
L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! +
L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}),
$$
which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately
translates to the following recursive algorithms for both ranking and unranking
(described for example in \cite{knuth:sas}):

\alg $\<Rank>(\pi,i,n,A)$: Compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
\id{rankalg}
\algo
\:If $i\ge n$, return~0.
\:$a\=R_A(\pi[i])$.
\:$b\=\<Rank>(\pi,i+1,n,A \setminus \{\pi[i]\})$.
\:Return $a\cdot(n-i)! + b$.
\endalgo

\>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
$L(\pi,[n])$.

\alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i\ldots n]$ is the $j$-th permutation on~$A$.
\id{unrankalg}
\algo
\:If $i>n$, return $(0,\ldots,0)$.
\:$x\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
\:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{x\})$.
\:$\pi[i]\=x$.
\: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])$.

\paran{Representation of sets}%
The most time-consuming parts of the above algorithms are of course operations
on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity
of the whole algorithm is easy to calculate:

\lemma\id{ranklemma}%
Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence
of deletions, which supports ranking and unranking of elements, and that
the time complexity of a~single operation is at most~$t(n)$.
Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$.

If we store~$A$ in an~ordinary array, we have insertion and deletion in constant time,
but ranking and unranking in~$\O(n)$, so $t(n)=\O(n)$ and the algorithm is quadratic.
Binary search trees give $t(n)=\O(\log n)$. The data structure of Dietz \cite{dietz:oal}
improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equivalent
to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$,
the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$.

To obtain linear time complexity, we will make use of the representation of
vectors by integers on the RAM as developed in Section~\ref{ramds}. We observe
that since the words of the RAM need to be able to hold integers as large as~$n!$,
the word size must be at least $\log n! = \Theta(n\log n)$. Therefore the whole
set~$A$ fits in~$\O(1)$ words and we get:

\thmn{Lexicographic ranking of permutations}
When we order the permutations on the set~$[n]$ lexicographically, both ranking
and unranking can be performed on the RAM in time~$\O(n)$.

\paran{The case of $k$-permutations}%
Our algorithm can be also generalized to lexicographic ranking of
\df{$k$-permutations,} that is of ordered $k$-tuples of distinct elements drawn from the set~$[n]$.
There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$
such $k$-permutations and they have a~recursive structure similar to the one of
the permutations.
Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no
longer rely on the same data structure fitting in a constant number of word-sized integers.
For example, if $k=1$, the ranks are $\O(\log n)$-bit numbers, but the data
structure still requires $\Theta(n\log n)$ bits.

We do a minor side step by remembering the complement of~$A$ instead, that is
the set of the at most~$k$ elements we have already seen. We will call this set~$H$
(because it describes the ``holes'' in~$A$). Since $\Omega(k\log n)$ bits are needed
to represent the rank, the vector representation of~$H$ certainly fits in a~constant
number of words. When we translate the operations on~$A$ to operations on~$H$,
again stored as a~vector, we get:

\thmn{Lexicographic ranking of $k$-permutations}
When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both
ranking and unranking can be performed on the RAM in time~$\O(k)$.

\section{Restricted permutations}

Another interesting class of combinatorial objects that can be counted and
ranked are restricted permutations. An~archetypal member of this class are
permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}
We will present a~general (un)ranking method for any class of restricted
permutations and derive a~linear-time algorithm for the derangements from it.

\defn\id{permnota}%
We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
all~permutations on~$[n]$.
A~\df{restriction graph} is a~bipartite graph~$G$ whose parts are two copies
of the set~$[n]$. A~permutation $\pi\in{\cal P}$ satisfies the restrictions
if $(i,\pi(i))$ is an~edge of~$G$ for every~$i$.

\paran{Equivalent formulations}%
We will follow the path unthreaded by Kaplansky and Riordan
\cite{kaplansky:rooks} and charted by Stanley in \cite{stanley:econe}.
We will relate restricted permutations to placements of non-attacking
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

\obs\id{rooksobs}%
The traces of permutations (and thus the permutations themselves) correspond
exactly to placements of $n$ rooks at the board in a~way such that the rooks do
not attack each other (i.e., there is at most one rook in every row and
likewise in every column; as there are $n$~rooks, there must be exactly one of them in
every row and column). When speaking about \df{rook placements,} we will always
mean non-attacking placements.

Restricted permutations then correspond to placements of rooks on a~board with
some of the squares removed. The \df{holes} (missing squares) correspond to the
non-edges of~$G$, so $\pi\in{\cal P}$ satisfies the restrictions iff
$T(\pi)$ avoids the holes.

Placements of~$n$ rooks (and therefore also restricted permutations) can be
also equated with perfect matchings in the restriction graph~$G$. The edges
of the matching correspond to the squares occupied by the rooks, the condition
that no two rooks share a~row nor column translates to the edges not touching
each other, and the use of exactly~$n$ rooks is equivalent to the matching
being perfect.

There is also a~well-known correspondence between the perfect matchings
in a~bipartite graph and non-zero summands in the formula for the permanent
of the bipartite adjacency matrix~$M$ of the graph. This holds because the
non-zero summands are in one-to-one correspondence with the placements
of~$n$ rooks on the corresponding board. The number of restricted
permutations is therefore equal to the permanent of the matrix~$M$.

The diversity of the characterizations of restricted permutations brings
both good and bad news. The good news is that we can use the
plethora of known results on bipartite matchings. Most importantly, we can efficiently
determine whether there exists at least one permutation satisfying a~given set of restrictions:

\thm
There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
a~permutation satisfying a~given restriction graph. The $n$ and~$m$ are the number
of vertices and edges of the restriction graph.

The bad news is that computing the permanent is known to be~$\#\rm P$-complete even
for zero-one matrices (as proven by Valiant \cite{valiant:permanent}).
As a~ranking function for a~set of~matchings can be used to count all such
matchings, we obtain the following theorem:

\thm\id{pcomplete}%
If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
a~set of restrictions which is a~part of the input, then $\rm P=\#P$.

However, the hardness of computing the permanent is the only obstacle.
We show that whenever we are given a~set of restrictions for which
the counting problem is easy (and it is also easy for subgraphs obtained
by deleting vertices), ranking is easy as well. The key will be once again
a~recursive structure, similar to the one we have seen in the case of plain
permutations in \ref{permrec}. We get:

\thmn{Lexicographic ranking of restricted permutations}
Suppose that we have a~family of matrices ${\cal M}=\{M_1,M_2,\ldots\}$ such that $M_n\in \{0,1\}^{n\times n}$
and it is possible to calculate the permanent of~$M'$ in time $\O(t(n))$ for every matrix $M'$
obtained by deletion of rows and columns from~$M_n$. Then there exist algorithms
for ranking and unranking in ${\cal P}_{A,M_n}$ in time $\O(n^4 + n^2\cdot t(n))$
if $M_n$ and an~$n$-element set~$A$ are given as a~part of the input.

Our time bound for ranking of general restricted permutations section is obviously very coarse.
Its main purpose was to demonstrate that many special cases of the ranking problem can be indeed computed in polynomial time.
For most families of restriction matrices, we can do much better. These speedups are hard to state formally
in general (they depend on the structure of the matrices), but we demonstrate them on the
specific case of derangements. We show that each matrix can be sufficiently characterized
by two numbers: the order of the matrix and the number of zeroes in it. We find a~recurrent
formula for the permanent, based on these parameters, which we use to precalculate all
permanents in advance. When we plug it in the general algorithm, we get:

\thmn{Ranking of derangements}%
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}

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$,
minor-closed classes, and graphs whose edge weights are
integers. Using randomness also helps, as does having the edges pre-sorted.

If we do not know anything about the structure of the graph and we are only allowed
to compare the edge weights, we can use the Pettie's MST algorithm.
Its time complexity is guaranteed to be asymptotically optimal,
but we do not know what it really is --- the best what we have is
an~$\O(m\timesalpha(m,n))$ upper bound and the trivial $\Omega(m)$ lower bound.

One thing we however know for sure. The algorithm runs on the weakest of our
computational models ---the Pointer Machine--- and its complexity is linear
in the minimum number of comparisons needed to decide the problem. We therefore
need not worry about the details of computational models, which have contributed
so much to the linear-time algorithms for our special cases. Instead, it is sufficient
to study the complexity of MST decision trees. However, not much is known about these trees so far.

As for the dynamic algorithms, we have an~algorithm which maintains the minimum
spanning forest within poly-logarithmic time per operation.
The optimum complexity is once again undecided --- the known lower bounds are very far
from the upper ones.
The known algorithms run on the Pointer machine and we do not know if using a~stronger
model can help.

For the ranking problems, the situation is completely different. We have shown
linear-time algorithms for three important problems of this kind. The techniques,
which we have used, seem to be applicable to other ranking problems. On the other
hand, ranking of general restricted permutations has turned out to balance on the
verge of $\#{\rm P}$-completeness. All our algorithms run
on the RAM model, which seems to be the only sensible choice for problems of
inherently arithmetic nature. While the unit-cost assumption on arithmetic operations
is not universally accepted, our results imply that the complexity of our algorithm
is dominated by the necessary arithmetics.

Aside from the concrete problems we have solved, we have also built several algorithmic
techniques of general interest: the unification procedures using pointer-based
bucket sorting and the vector computations on the RAM. We hope that they will
be useful in many other algorithms.

\chapter{Bibliography}

\dumpbib

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

\bye