\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
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))$.
\problemn{Dynamic connectivity}
Maintain an~undirected graph under a~sequence of the following operations:
\itemize\ibull
-\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
-The structure could support dynamic addition and removal of vertices, too,
-but this is easy to add and infrequently used, so we will rather keep the set
-of vertices fixed for clarity.}
+\:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
+(It is possible to modify the structure to support dynamic addition and removal of vertices, too.)
\:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
identifier. This assumes that the edge did not exist yet.
\:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
\:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
\endlist
-In this chapter, we will focus on the dynamic version of the minimum spanning forest.
+\>In this chapter, we will focus on the dynamic version of the minimum spanning forest.
This problem seems to be intimately related to the dynamic connectivity. Indeed, all known
algorithms for dynamic connectivity maintain some sort of a~spanning forest.
This suggests that a~dynamic MSF algorithm could be obtained by modifying the
\paran{Fully dynamic MSF}%
The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
-reduction whose properties are summarized in the following theorem:
+reduction of Holm et al.:
\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
Suppose that we have a~decremental MSF algorithm with the following properties:
comparisons are certainly not sufficient to determine the second best spanning tree. We will
assume that our computation model is able to add, subtract and compare the edge weights
in constant time.
-
Let us focus on finding the second lightest spanning tree first.
\paran{Second lightest spanning tree}%
\lemma
For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find
edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum.
-
-\nota
-We will call this procedure \df{finding the best exchange in $(H,T)$.}
+(We will call this procedure \df{finding the best exchange in $(H,T)$.})
\cor
Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
Once we know~$T_1$ and~$T_2$, how to get~$T_3$? According to the Difference lemma, $T_3$~can be
obtained by a~single exchange from either~$T_1$ or~$T_2$. Therefore we need to find the
best exchange for~$T_2$ and the second best exchange for~$T_1$ and use the better of them.
-The latter is not easy to find directly, but we can get around it:
+The latter is not easy to find directly, so we observe:
\obs\id{tbobs}%
The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
\paran{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\foot{This graph is always derived from~$G$ by a~sequence of edge deletions
-and contractions. It is tempting to say that it is a~minor of~$G$, but this is not true as we
-preserve multiple edges.} and its minimum spanning tree. The root node contains~$(G,T_1)$,
+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
\paran{Invariant edges}%
Our algorithm can be further improved for small values of~$K$ (which seems to be the common
case in most applications) by the reduction of Eppstein \cite{eppstein:ksmallest}.
-We will observe that there are many edges of~$T_1$
+He has proven that there are many edges of~$T_1$
which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
many edges of $G\setminus T_1$ which are excluded from all those spanning trees.
When we combine this with the previous construction, we get the following theorem:
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$.
+
%--------------------------------------------------------------------------------
-\chapter{Ranking Combinatorial Structures}\id{rankchap}%
+\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}):
-\chapter{Bibliography}
+\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