\input macros.tex
-\finalfalse %%FIXME
+\input fonts10.tex
-\def\rawchapter#1{\vensure{0.5in}\bigbreak\bigbreak
+\finaltrue
+\hwobble=0mm
+\advance\hsize by 1cm
+\advance\vsize by 20pt
+
+\def\rawchapter#1{\vensure{0.5in}\bigskip\goodbreak
\leftline{\chapfont #1}
}
-\def\rawsection#1{\bigskip
+\def\rawsection#1{\medskip\smallskip
\leftline{\secfont #1}
\nobreak
-\medskip
+\smallskip
\nobreak
}
-\chapter{Introduction}
-\bigskip
+\def\schapter#1{\chapter{#1}\medskip}
+
+\schapter{Introduction}
This thesis tells the story of two well-established problems of algorithmic
graph theory: the minimum spanning trees and ranks of permutations. At distance,
itself.
We have tried to cover all known important results on both problems and unite them
-in a~single coherent theory. At many places, we have attempted to contribute my own
+in a~single coherent theory. At many places, we have attempted to contribute our own
little stones to this mosaic: several new results, simplifications of existing
ones, and last, but not least filling in important details where the original
authors have missed some.
\endalgo
\thm
-The Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
+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))$.\foot{Here $\alpha(m,n)$ is a~certain inverse of the Ackermann's
-function.}
+$\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's
+function.
\section{Contractive algorithms}\id{contalg}%
\:$\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.}
+\::$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))$.
+The Contractive Bor\o{u}vka's algorithm finds the MST of the graph given as
+its input in time $\O(\min(n^2,m\log n))$.
We also show that this time bound is tight --- we construct an~explicit
family of graphs on which the algorithm spends $\Theta(m\log n)$ steps.
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.
+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
Our formal definition is closely related to the \em{linking automaton} proposed
by Knuth in~\cite{knuth:fundalg}.
-\section{Pointer machine techniques}\id{bucketsort}%
+\section{Bucket sorting and related techniques}\id{bucketsort}%
In the Contractive Bor\o{u}vka's algorithm, we needed to contract a~given
set of edges in the current graph and then flatten the graph, all this in time $\O(m)$.
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
+a~bunch of pointer-based sorting techniques which can be summarized by the following
lemma:
\lemma
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,
+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
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.
+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
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}%
\section{Minor-closed graph classes}\id{minorclosed}%
The contractive algorithm given in Section~\ref{contalg} has been found to perform
-well on planar graphs, but in the general case its time complexity was not linear.
-Can we find any broader class of graphs where this algorithm is still efficient?
-The right context turns out to be the minor-closed graph classes, which are
+well on planar graphs, but in general its time complexity was not linear.
+Can we find any broader class of graphs where the linear bound holds?
+The right context turns out to be the minor-closed classes, which are
closed under contractions and have bounded density.
\defn\id{minordef}%
\example
Non-trivial minor-closed classes include:
-\itemize\ibull
-\:planar graphs,
-\:graphs embeddable in any fixed surface (i.e., graphs of bounded genus),
-\:graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles,
-\:graphs of bounded tree-width or path-width.
-\endlist
+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
Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph
with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$.
-So we get the following algorithm:
+This leads to the following algorithm:
\algn{Local Bor\o{u}vka's Algorithm, Mare\v{s} \cite{mm:mst}}%
\algo
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~part of the MST edges and contracts
+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 run the Jarn\'\i{}k's algorithm, we find the MST in time $\O(m\log\log n)$.
+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.
We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
we conserve the current tree and start with a~different vertex and an~empty heap. When this
process runs out of vertices, it has identified a~sub-forest of the MST, so we can
-contract the edges of~this forest and iterate.
-
-\algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{itjar}%
-\algo
-\algin A~graph~$G$ with an edge comparison oracle.
-\:$T\=\emptyset$. \cmt{edges of the MST}
-\:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
-\:$m_0\=m$.
-\:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
-\::$F\=\emptyset$. \cmt{forest built in the current phase}
-\::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
-\::While there is a~vertex $v_0\not\in F$:
-\:::Run the Jarn\'\i{}k's algorithm from~$v_0$, stop when:
-\::::all vertices have been processed, or
-\::::a~vertex of~$F$ has been added to the tree, or
-\::::the heap has grown to more than~$t$ elements.
-\:::Denote the resulting tree~$R$.
-\:::$F\=F\cup R$.
-\::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
-\::Contract all edges of~$F$ and flatten~$G$.
-\algout Minimum spanning tree~$T$.
-\endalgo
+contract the edges of~this forest and iterate. This improves the time complexity
+significantly:
\thm\id{itjarthm}%
The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
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}.
+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.
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 infer the peaks from their results can be decreased,
+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 in this abstract and state only the final theorem:
+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)$.
-\rem
-Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown that linear-time
-verification can be achieved even on the Pointer Machine.
-They combine an~algorithm of time complexity $\O(m\timesalpha(m,n))$
-based on the Disjoint Set Union data structure with the framework of topological graph
-computations described in Section \ref{bucketsort}.
-The online version of this problem has turned out to be more difficult: there
-is a~super-linear lower bound for it due to Pettie \cite{pettie:onlineverify}.
-
\section{A randomized algorithm}\id{randmst}%
When we analysed the Contractive Bor\o{u}vka's algorithm in Section~\ref{contalg},
\algout The minimum spanning forest of~$G$.
\endalgo
-A~careful analysis of this algorithm, based on properties of its recursion tree
-and the peak-finding algorithm of the previous section yields the following time bounds:
+\>A~careful analysis of this algorithm, based on properties of its recursion tree
+and on the peak-finding algorithm of the previous section, yields the following time bounds:
\thm
The KKT algorithm runs in time $\O(\min(n^2,m\log n))$ in the worst case on the RAM.
-
-\thm
-The expected time complexity of the KKT algorithm on the RAM is $\O(m)$.
+The expected time complexity is $\O(m)$.
\chapter{Approaching Optimality}\id{optchap}%
\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 rule serves to identify
-edges that belong to the MST, while all other edges are left in the process. This
-unfortunately means that the later stages of computation spend most of
-their time on these edges that never enter the MSF. A~notable exception is the randomized
-algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses
-the Red rule (Lemma \ref{redlemma}) to filter out edges that are guaranteed to stay
-outside the MST, so that the graphs with which the algorithm works get smaller
-with time.
-
-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.
+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
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$.
-The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
-moment at most~$\varepsilon n$ elements of the $n$~elements inserted can be
-corrupted.
-
-\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
-\>We describe the exact mechanics of the soft heaps and analyse its complexity.
-The important properties are summarized in the following theorem:
+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
\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 this algorithm, preferably in the earlier
-version without Fibonacci heaps as the soft heap lacks the \<Decrease> operation.
+algorithm in place of a~normal heap. We can for example try implanting the soft heap
+in the Jarn\'i{}k's algorithm, preferably in the earlier
+version without Fibonacci heaps as the soft heaps lack the \<Decrease> operation.
This brave, but somewhat simple-minded attempt is however doomed to
-fail. The reason is of course the corruption of items inside the heap, which
-leads to increase of weights of some subset of edges. In presence of corrupted
-edges, most of the theory we have so carefully built breaks down. There is
-fortunately some light in this darkness. While the basic structural properties
-of MST's no longer hold, 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.
+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,
\lemman{Generalized contraction}
When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$.
-We can now bring corruption back to the game and state a~``robust'' version
-of this lemma. A~notation for corrupted graphs will be handy:
+Let us bring corruption back to the game and state a~``robust'' version
+of this lemma.
\nota\id{corrnota}%
When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
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 mimic the Iterated Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
+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.
+%%The following theorem describes the properties of this partition:
\thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
trees constructed by brute force for very small subgraphs.
-Formally, the decision trees are defined as follows:
+%%Formally, the decision trees are defined as follows:
+Let us define them first:
\defnn{Decision trees and their complexity}\id{decdef}%
A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
problem in all other comparison-based models.
The downside is that we do not know any explicit construction of the optimal
-decision trees, or at least a~non-constructive proof of their complexity.
+decision trees, nor even a~non-constructive proof of their complexity.
On the other hand, the complexity of any existing comparison-based algorithm
can be used as an~upper bound on the decision tree complexity. Also, we can
construct an~optimal decision tree using brute force:
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. When the procedure is
-called on a~graph~$G$, it sets the parameter~$t$ to roughly $\log^{(3)} n$ and
-it calls the \<Partition> procedure to split the graph into a~collection of
-clusters of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision
-trees to find the MSF of the clusters. The graph obtained by contracting
-the clusters is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's
-algorithm runs on it in linear time. Afterwards we combine the MSF's of the clusters
-and of the contracted graphs, we mix in the corrupted edges and run two iterations
-of the Contractive Bor\o{u}vka's algorithm. This guarantees reduction in the number of
-both vertices and edges by a~constant factor, so we can efficiently recurse on the
-resulting graph.
+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 \<Partition> (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
+\: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}).
+\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (see Section \ref{iteralg}).
\:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
\:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
\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:
+\>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, we prove:
\thm
The time complexity of the Optimal algorithm is $\Theta(D(m,n))$.
optimal algorithm:
\thm
-The time complexity of the Optimal algorithm is $\O(m\alpha(m,n))$.
+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\}$.
+(It is possible to modify the structure to support dynamic addition and removal of vertices, too.)
+\:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
+identifier. This assumes that the edge did not exist yet.
+\:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
+\:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
+\endlist
+
+\>In this chapter, we will focus on the dynamic version of the minimum spanning forest.
+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 of Holm et al.:
+
+\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
+Suppose that we have a~decremental MSF algorithm with the following properties:
+\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.
+(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, so we observe:
+
+\obs\id{tbobs}%
+The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
+
+\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}.
+He has proven that there are many edges of~$T_1$
+which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
+many edges of $G\setminus T_1$ which are excluded from all those spanning trees.
+When we combine this with the previous construction, we get the following theorem:
+
+\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}%
-\chapter{Bibliography}
+\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.
+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])$ 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
+A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
+A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares \hbox{$T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.}
+
+\obs\id{rooksobs}%
+The traces of permutations (and thus the permutations themselves) correspond
+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.
+
+\schapter{Conclusions}
+
+We have seen the many facets of the minimum spanning tree problem. It has
+turned out that while the major question of the existence of a~linear-time
+MST algorithm is still open, backing off a~little bit in an~almost arbitrary
+direction leads to a~linear solution. This includes classes of graphs with edge
+density at least $\lambda_k(n)$ (the $k$-th row inverse of the Ackermann's function) for an~arbitrary fixed~$k$,
+minor-closed classes, and graphs whose edge weights are
+integers. Using randomness also helps, as does having the edges pre-sorted.
+
+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.
+
+\schapter{Bibliography}
\dumpbib
projects / saga.git / blobdiff