7 \font\chapfont=csb14 at 16pt
8 \def\rawchapter#1{\vensure{0.5in}\bigskip\goodbreak
9 \leftline{\chapfont #1}
12 \def\rawsection#1{\medskip\smallskip
13 \leftline{\secfont #1}
19 \def\schapter#1{\chapter{#1}\medskip}
21 \schapter{Introduction}
23 This thesis tells the story of two well-established problems of algorithmic
24 graph theory: the minimum spanning trees and ranks of permutations. At distance,
25 both problems seem to be simple, boring and already solved, because we have poly\-nom\-ial-time
26 algorithms for them since ages. But when we come closer and seek algorithms that
27 are really efficient, the problems twirl and twist and withstand many a~brave
28 attempt at the optimum solution. They also reveal a~vast and diverse landscape
29 of a~deep and beautiful theory. Still closer, this landscape turns out to be interwoven
30 with the intricate details of various models of computation and even of arithmetics
33 We have tried to cover all known important results on both problems and unite them
34 in a~single coherent theory. At many places, we have attempted to contribute my own
35 little stones to this mosaic: several new results, simplifications of existing
36 ones, and last, but not least filling in important details where the original
37 authors have missed some.
39 When compared with the earlier surveys on the minimum spanning trees, most
40 notably Graham and Hell \cite{graham:msthistory} and Eisner \cite{eisner:tutorial},
41 this work adds many of the recent advances, the dynamic algorithms and
42 also the relationship with computational models. No previous work covering
43 the ranking problems in their entirety is known.
45 We~have tried to stick to the usual notation except where it was too inconvenient.
46 Most symbols are defined at the place where they are used for the first time.
47 To avoid piling up too many symbols at places that speak about a~single fixed graph,
48 this graph is always called~$G$, its set of vertices and edges are denoted by $V$
49 and~$E$ respectively, and we~also use~$n$ for the number of its vertices and $m$~for
50 the number of edges. At places where there could be a~danger of confusion, more explicit notation
53 \chapter{Minimum Spanning Trees}
57 The problem of finding a minimum spanning tree of a weighted graph is one of the
58 best studied problems in the area of combinatorial optimization since its birth.
59 Its colorful history (see \cite{graham:msthistory} and \cite{nesetril:history} for the full account)
60 begins in~1926 with the pioneering work of Bor\o{u}vka
61 \cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
62 who studied primarily an Euclidean version of the problem related to planning
63 of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
64 algorithm for the general version of the problem. As it was well before the dawn of graph
65 theory, the language of his paper was complicated, so we will better state the problem
66 in contemporary terminology:
68 \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
69 find its minimum spanning tree, defined as follows:
72 For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
74 \:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
75 \:A~\df{spanning tree} of~$G$ is any spanning subgraph of~$G$ that is a tree.
76 \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
77 \:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$
78 is the smallest possible among all the spanning trees of~$G$.
79 \:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as
80 a union of (minimum) spanning trees of its connected components.
83 Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
84 mostly geometric setting, and he has discovered another efficient algorithm.
85 In the next 50 years, several significantly faster algorithms were published, ranging
86 from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
87 over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
88 and Pettie \cite{pettie:ackermann}, to an~algorithm by Pettie \cite{pettie:optimal}
89 whose time complexity is provably optimal.
91 Before we discuss the algorithms, let us review the basic properties of spanning trees.
92 We will mostly follow the theory developed by Tarjan in~\cite{tarjan:dsna} and show
93 that the weights on edges are not necessary for the definition of the MST.
95 \defnn{Heavy and light edges}\id{heavy}%
96 Let~$G$ be a~connected graph with edge weights~$w$ and $T$ its spanning tree. Then:
98 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ with~$y$.
99 \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
100 the edges of this path \df{edges covered by~$e$}.
101 \:An edge~$e$ is called \df{light with respect to~$T$} (or just \df{$T$-light}) if it covers a~heavier edge, i.e., if there
102 is an~edge $f\in T[e]$ such that $w(f) > w(e)$.
103 \:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge.
107 A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
110 If all edge weights are distinct, then the minimum spanning tree is unique.
113 When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
114 its unique minimum spanning tree.
115 To simplify the description of MST algorithms, we will assume that the weights
116 of all edges are distinct and that instead of numeric weights we are given a~\df{comparison oracle.}
117 The oracle is a~function that answers questions of type ``Is $w(e)<w(f)$?'' in
118 constant time. This will conveniently shield us from problems with representation
119 of real numbers in algorithms and in the few cases where we need a more concrete
120 input, we will explicitly state so. In case the weights are not distinct, the ties
121 can be broken arbitrarily.
123 \section{Classical algorithms}
125 The characterization of MST's in terms of light edges makes it easy to develop
126 the Tarjan's Red-Blue meta-algorithm, which is based on the following properties:
128 \lemman{Blue lemma, also known as the Cut rule}\id{bluelemma}%
129 The lightest edge of every cut is contained in the MST.
131 \lemman{Red lemma, also known as the Cycle rule}\id{redlemma}%
132 An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.
134 The algorithm repeatedly colors lightest edges of cuts blue and heaviest
135 edges of cycles red. We prove that no matter which order of the colorings
136 we use, the algorithm always stops and the blue edges form the MST.
138 All three classical MST algorithms (Bor\o{u}vka's, Jarn\'\i{}k's and Kruskal's)
139 can be then obtained as specializations of this procedure. We also calculate the
140 time complexity of standard implementations of these algorithms.
142 \algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst}, and others}
144 \algin A~graph~$G$ with an edge comparison oracle.
145 \:$T\=$ a forest consisting of vertices of~$G$ and no edges.
146 \:While $T$ is not connected, perform a~\df{Bor\o{u}vka step:}
147 \::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
148 separating $T_i$ from the rest of~$T$.
149 \::Add all $e_i$'s to~$T$.
150 \algout Minimum spanning tree~$T$.
154 The Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
156 \algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}%
158 \algin A~graph~$G$ with an edge comparison oracle.
159 \:$T\=$ a single-vertex tree containing an~arbitrary vertex of~$G$.
160 \:While there are vertices outside $T$:
161 \::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
163 \algout Minimum spanning tree~$T$.
167 The Jarn\'\i{}k's algorithm computes the MST of a~given graph in time $\O(m\log n)$.
169 \algn{Kruskal \cite{kruskal:mst}}
171 \algin A~graph~$G$ with an edge comparison oracle.
172 \:Sort edges of~$G$ by their increasing weights.
173 \:$T\=\hbox{an empty spanning subgraph}$.
174 \:For all edges $e$ in their sorted order:
175 \::If $T+e$ is acyclic, add~$e$ to~$T$.
176 \::Otherwise drop~$e$.
177 \algout Minimum spanning tree~$T$.
181 The Kruskal's algorithm finds the MST of the graph given as input in time $\O(m\log n)$.
182 If the edges are already sorted by their weights, the time drops to
183 $\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's
186 \section{Contractive algorithms}\id{contalg}%
188 While the classical algorithms are based on growing suitable trees, they
189 can be also reformulated in terms of edge contraction. Instead of keeping
190 a~forest of trees, we can keep each tree contracted to a single vertex.
191 This replaces the relatively complex tree-edge incidencies by simple
192 vertex-edge incidencies, potentially speeding up the calculation at the
193 expense of having to perform the contractions.
194 A~contractive version of the Bor\o{u}vka's algorithm is easy to formulate
197 \algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor}%
199 \algin A~graph~$G$ with an edge comparison oracle.
201 \:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize edge labels.}
203 \::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$.
204 \::$T\=T\cup \{ \ell(e_1),\ldots,\ell(e_n) \}$.\cmt{Remember labels of all selected edges.}
205 \::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$.}
206 \::Flatten $G$ (remove parallel edges and loops).
207 \algout Minimum spanning tree~$T$.
211 The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
212 time $\O(\min(n^2,m\log n))$.
214 We also show that this time bound is tight --- we construct an~explicit
215 family of graphs on which the algorithm spends $\Theta(m\log n)$ steps.
216 Given a~planar graph, the algorithm however runs much faster (we get a~linear-time
217 algorithm much simpler than the one of Matsui \cite{matsui:planar}):
220 When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
223 Graph contractions are indeed a~very powerful tool and they can be used in other MST
224 algorithms as well. The following lemma shows the gist:
226 \lemman{Contraction lemma}\id{contlemma}%
227 Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
228 produced by contracting~$e$ in~$G$, and $\pi$ the bijection between edges of~$G-e$ and
229 their counterparts in~$G/e$. Then $\mst(G) = \pi^{-1}[\mst(G/e)] + e.$
231 \chapter{Fine Details of Computation}
233 \section{Models and machines}
235 Traditionally, computer scientists have been using a~variety of computational models
236 as a~formalism in which their algorithms are stated. If we were studying
237 NP-complete\-ness, we could safely assume that all these models are equivalent,
238 possibly up to polynomial slowdown which is negligible. In our case, the
239 differences between good and not-so-good algorithms are on a~much smaller
240 scale, so we need to state our computation models carefully and develop
241 a repertoire of basic data structures tailor-made for the fine details of the
242 models. In recent decades, most researchers in the area of combinatorial algorithms
243 have been considering the following two computational models, and we will do likewise.
245 The \df{Random Access Machine (RAM)} is not a~single coherent model, but rather a~family
246 of closely related machines (See Cook and Reckhow \cite{cook:ram} for one of the usual formal definitions
247 and Hagerup \cite{hagerup:wordram} for a~thorough description of the differences
248 between the RAM variants.) We will consider the variant usually called the \df{Word-RAM.}
249 It allows the ``C-language operators'', i.e., arithmetics and bitwise logical operations,
250 running in constant time on words of a~specified size.
252 The \df{Pointer Machine (PM)} also does not seem to have any well established definition.
253 The various kinds of pointer machines are examined by Ben-Amram in~\cite{benamram:pm},
254 but unlike the RAM's they turn out to be equivalent up to constant slowdown.
255 Our formal definition is closely related to the \em{linking automaton} proposed
256 by Knuth in~\cite{knuth:fundalg}.
258 \section{Bucket sorting and related techniques}\id{bucketsort}%
260 In the Contractive Bor\o{u}vka's algorithm, we needed to contract a~given
261 set of edges in the current graph and then flatten the graph, all this in time $\O(m)$.
262 This can be easily handled on both the RAM and the PM by bucket sorting. We develop
263 a~bunch of pointer-based sorting techniques which can be summarized by the following
267 Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are
268 arbitrary pointers and symbols from a~finite alphabet, to equality classes can
269 be performed on the Pointer Machine in time $\O(n + \sum_i \vert S_i \vert)$.
272 A~direct consequence of this unification is a~linear-time algorithm for subtree
273 isomorphism, significantly simpler than the standard one due to Zemlayachenko (see \cite{zemlay:treeiso}
274 and also Dinitz et al.~\cite{dinitz:treeiso}). When we apply a~similar technique
275 to general graphs, we get the framework of topological graph computation
276 of Buchsbaum et al.~\cite{buchsbaum:verify}.
279 A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of
280 vertices and edges can be arbitrary symbols drawn from a~finite alphabet. The output
281 of the computation is another labeling of the same graph. This time, the vertices and
282 edges can be labeled with not only symbols of the alphabet, but also with pointers to the vertices
283 and edges of the input graph, and possibly also with pointers to outside objects.
284 A~graph computation is called \df{topological} if it produces isomorphic
285 outputs for isomorphic inputs. The isomorphism of course has to preserve not only
286 the structure of the graph, but also the labels in the obvious way.
289 For a~collection~$\C$ of graphs, we define $\vert\C\vert$ as the number of graphs in
290 the collection and $\Vert\C\Vert$ as their total size, i.e., $\Vert\C\Vert = \sum_{G\in\C} n(G) + m(G)$.
293 Suppose that we have a~topological graph computation~$\cal T$ that can be performed in time
294 $T(k)$ for graphs on $k$~vertices. Then we can run~$\cal T$ on a~collection~$\C$
295 of labeled graphs on~$k$ vertices in time $\O(\Vert\C\Vert + (k+s)^{k(k+2)}\cdot (T(k)+k^2))$,
296 where~$s$ is a~constant depending only on the number of symbols used as vertex/edge labels.
298 \section{Data structures on the RAM}\id{ramds}%
300 There is a~lot of data structures designed specifically for the RAM. These structures
301 take advantage of both indexing and arithmetics and they often surpass the known
302 lower bounds for the same problem on the~PM. In many cases, they achieve constant time
303 per operation, at least when either the magnitude of the values or the size of
304 the data structure is suitably bounded.
306 A~classical result of this type is the tree of van Emde Boas~\cite{boas:vebt}
307 which represents a~subset of the integers $\{0,\ldots,U-1\}$. It allows insertion,
308 deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
309 regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
310 algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
311 for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
312 where $w_{max}$ is the maximum weight.
314 A~real breakthrough has however been made by Fredman and Willard who introduced
315 the Fusion trees~\cite{fw:fusion}. They again perform membership and predecessor
316 operation on a~set of $n$~integers, but with time complexity $\O(\log_W n)$
317 per operation on a~Word-RAM with $W$-bit words. This of course assumes that
318 each element of the set fits in a~single word. As $W$ must at least~$\log n$,
319 the operations take $\O(\log n/\log\log n)$ time and thus we are able to sort $n$~integers
320 in time~$o(n\log n)$. This was further improved by Han and Thorup \cite{han:detsort,hanthor:randsort}.
322 The Fusion trees themselves have very limited use in graph algorithms, but the
323 principles behind them are ubiquitous in many other data structures and these
324 will serve us well and often. We are going to build the theory of Q-heaps,
325 which will later lead to a~linear-time MST algorithm for arbitrary integer weights.
326 Other such structures will help us in building linear-time RAM algorithms for computing the ranks
327 of various combinatorial structures in Chapter~\ref{rankchap}.
329 Outside our area, important consequences of RAM data structures include the
330 Thorup's $\O(m)$ algorithm for single-source shortest paths in undirected
331 graphs with positive integer weights \cite{thorup:usssp} and his $\O(m\log\log
332 n)$ algorithm for the same problem in directed graphs \cite{thorup:sssp}. Both
333 algorithms have been then significantly simplified by Hagerup
336 Despite the progress in the recent years, the corner-stone of all RAM structures
337 is still the representation of combinatorial objects by integers introduced by
339 First of all, we observe that we can encode vectors in integers:
341 \notan{Bit strings}\id{bitnota}%
342 We will work with binary representations of natural numbers by strings over the
343 alphabet $\{\0,\1\}$: we will use $\(x)$ for the number~$x$ written in binary,
344 $\(x)_b$ for the same padded to exactly $b$ bits by adding leading zeroes,
345 and $x[k]$ for the value of the $k$-th bit of~$x$ (with a~numbering of bits such that $2^k[k]=1$).
346 The usual conventions for operations on strings will be utilized: When $s$
347 and~$t$ are strings, we write $st$ for their concatenation and
348 $s^k$ for the string~$s$ repeated $k$~times.
349 When the meaning is clear from the context,
350 we will use $x$ and $\(x)$ interchangeably to avoid outbreak of symbols.
353 The \df{bitwise encoding} of a~vector ${\bf x}=(x_0,\ldots,x_{d-1})$ of~$b$-bit numbers
354 is an~integer~$x$ such that $\(x)=\(x_{d-1})_b\0\(x_{d-2})_b\0\ldots\0\(x_0)_b$. In other
355 words, $x = \sum_i 2^{(b+1)i}\cdot x_i$. (We have interspersed the elements with \df{separator bits.})
358 If we want to fit the whole vector in a~single machine word, the parameters $b$ and~$d$ must satisfy
359 the condition $(b+1)d\le W$ (where $W$~is the word size of the machine).
360 By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
361 We describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
362 on their codes. For example, we can handle element-wise comparison of vectors, insertion
363 in a~sorted vector or shuffling elements of a~vector according to a~fixed permutation,
364 all in $\O(1)$ time. This also implies that several functions on numbers can be performed
365 in constant time, most notably binary logarithms.
366 The vector operations then serve as building blocks for construction of the Q-heaps. We get:
369 Let $W$ and~$k$ be positive integers such that $k=\O(W^{1/4})$. Let~$Q$
370 be a~Q-heap of at most $k$-elements of $W$~bits each. Then we can perform
371 Q-heap operations on~$Q$ (insertion, deletion, search for a~given value and search
372 for the $i$-th smallest element) in constant time on a~Word-RAM with word size~$W$,
373 after spending time $\O(2^{k^4})$ on the same RAM on precomputing of tables.
376 For every positive integer~$r$ and $\delta>0$ there exists a~data structure
377 capable of maintaining the minimum of a~set of at most~$r$ word-sized numbers
378 under insertions and deletions. Each operation takes $\O(1)$ time on a~Word-RAM
379 with word size $W=\Omega(r^{\delta})$, after spending time
380 $\O(2^{r^\delta})$ on precomputing of tables.
382 \chapter{Advanced MST Algorithms}
384 \section{Minor-closed graph classes}\id{minorclosed}%
386 The contractive algorithm given in Section~\ref{contalg} has been found to perform
387 well on planar graphs, but in the general case its time complexity was not linear.
388 Can we find any broader class of graphs where this algorithm is still efficient?
389 The right context turns out to be the minor-closed graph classes, which are
390 closed under contractions and have bounded density.
393 A~graph~$H$ is a \df{minor} of a~graph~$G$ (written as $H\minorof G$) iff it can be obtained
394 from a~subgraph of~$G$ by a sequence of simple graph contractions.
397 A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and
398 every minor~$H$ of~$G$, the graph~$H$ lies in~$\cal C$ as well. A~class~$\cal C$ is called
399 \df{non-trivial} if at least one graph lies in~$\cal C$ and at least one lies outside~$\cal C$.
402 Non-trivial minor-closed classes include:
404 graphs embeddable in any fixed surface (i.e., graphs of bounded genus),
405 graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles,
406 and graphs of bounded tree-width or path-width.
409 Many of the nice structural properties of planar graphs extend to
410 minor-closed classes, too (see Lov\'asz \cite{lovasz:minors} for a~nice survey
411 of this theory and Diestel \cite{diestel:gt} for some of the deeper results).
412 For analysis of the contractive algorithm, we will make use of the bounded
413 density of minor-closed classes:
416 Let $G$ be a~graph and $\cal C$ be a class of graphs. We define the \df{edge density}
417 $\varrho(G)$ of~$G$ as the average number of edges per vertex, i.e., $m(G)/n(G)$. The
418 edge density $\varrho(\cal C)$ of the class is then defined as the infimum of $\varrho(G)$ over all $G\in\cal C$.
420 \thmn{Density of minor-closed classes, Mader~\cite{mader:dens}}
421 Every non-trivial minor-closed class of graphs has finite edge density.
423 \thmn{MST on minor-closed classes, Mare\v{s} \cite{mm:mst}}\id{mstmcc}%
424 For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
425 algorithm (\ref{contbor}) finds the MST of any graph of this class in time
426 $\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
428 \paran{Local contractions}\id{nobatch}%
429 The contractive algorithm uses ``batch processing'' to perform many contractions
430 in a single step. It is also possible to perform them one edge at a~time,
431 batching only the flattenings. A~contraction of an edge~$uv$ can be done in time~$\O(\deg(u))$,
432 so we have to make sure that there is a~steady supply of low-degree vertices.
433 It indeed is in minor-closed classes:
435 \lemman{Low-degree vertices}\id{lowdeg}%
436 Let $\cal C$ be a graph class with density~$\varrho$ and $G\in\cal C$ a~graph
437 with $n$~vertices. Then at least $n/2$ vertices of~$G$ have degree at most~$4\varrho$.
439 This leads to the following algorithm:
441 \algn{Local Bor\o{u}vka's Algorithm, Mare\v{s} \cite{mm:mst}}%
443 \algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$.
445 \:$\ell(e)\=e$ for all edges~$e$.
447 \::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
448 \:::Select the lightest edge~$e$ incident with~$v$.
450 \:::$T\=T + \ell(e)$.
451 \::Flatten $G$, removing parallel edges and loops.
452 \algout Minimum spanning tree~$T$.
456 When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the
457 Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$
458 finds the MST of any graph from this class in time $\O(n)$. (The constant
459 in the~$\O$ depends on~the class.)
461 \section{Iterated algorithms}\id{iteralg}%
463 We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
464 Fredman and Tarjan \cite{ft:fibonacci} have shown a~faster implementation using their Fibonacci
465 heaps, which runs in time $\O(m+n\log n)$. This is $\O(m)$ whenever the density of the
466 input graph reaches $\Omega(\log n)$. This suggests that we could combine the algorithm with
467 another MST algorithm, which identifies a~subset of the MST edges and contracts
468 them to increase the density of the graph. For example, if we perform several Bor\o{u}vka
469 steps and then we run the Jarn\'\i{}k's algorithm, we find the MST in time $\O(m\log\log n)$.
471 Actually, there is a~much better choice of the algorithms to combine: use the
472 Jarn\'\i{}k's algorithm with a~Fibonacci heap multiple times, each time stopping it after a~while.
473 A~good choice of the stopping condition is to place a~limit on the size of the heap.
474 We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
475 we conserve the current tree and start with a~different vertex and an~empty heap. When this
476 process runs out of vertices, it has identified a~sub-forest of the MST, so we can
477 contract the edges of~this forest and iterate.
479 \algn{Iterated Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{itjar}%
481 \algin A~graph~$G$ with an edge comparison oracle.
482 \:$T\=\emptyset$. \cmt{edges of the MST}
483 \:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
485 \:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
486 \::$F\=\emptyset$. \cmt{forest built in the current phase}
487 \::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
488 \::While there is a~vertex $v_0\not\in F$:
489 \:::Run the Jarn\'\i{}k's algorithm from~$v_0$, stop when:
490 \::::all vertices have been processed, or
491 \::::a~vertex of~$F$ has been added to the tree, or
492 \::::the heap has grown to more than~$t$ elements.
493 \:::Denote the resulting tree~$R$.
495 \::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
496 \::Contract all edges of~$F$ and flatten~$G$.
497 \algout Minimum spanning tree~$T$.
501 The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
502 $\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i \mid \log^{(i)}n \le m/n \}$.
505 The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
507 \paran{Integer weights}%
508 The algorithm spends most of the time in phases which have small heaps. Once the
509 heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
510 to guarantee that at most~$k$ phases remain. This means that if we are able to
511 construct a~heap of size $\Omega(\log^{(k)} n)$ with constant time per operation,
512 we can get a~linear-time algorithm for MST. This is the case when the weights are
513 integers (we can use the Q-heap trees from Section~\ref{ramds}).
515 \thmn{MST for integer weights, Fredman and Willard \cite{fw:transdich}}\id{intmst}%
516 MST of a~graph with integer edge weights can be found in time $\O(m)$ on the Word-RAM.
518 \section{Verification of minimality}\id{verifysect}%
520 Now we will turn our attention to a~slightly different problem: given a~spanning
521 tree, how to verify that it is minimum? We will show that this can be achieved
522 in linear time and it will serve as a~basis for a~randomized linear-time
523 MST algorithm in the next section.
525 MST verification has been studied by Koml\'os \cite{komlos:verify}, who has
526 proven that $\O(m)$ edge comparisons are sufficient, but his algorithm needed
527 super-linear time to find the edges to compare. Dixon, Rauch and Tarjan \cite{dixon:verify}
528 have later shown that the overhead can be reduced
529 to linear time on the RAM using preprocessing and table lookup on small
530 subtrees. Later, King has given a~simpler algorithm in \cite{king:verifytwo}.
532 To verify that a~spanning tree~$T$ is minimum, it is sufficient to check that all
533 edges outside~$T$ are $T$-heavy. For each edge $uv\in E\setminus T$, we will
534 find the heaviest edge of the tree path $T[u,v]$ (we will call it the \df{peak}
535 of the path) and compare its weight to $w(uv)$. We have therefore transformed
536 the MST verification to the problem of finding peaks for a~set of \df{query
537 paths} on a~given tree. By a~sequence of further transformations, we can even
538 assume that the given tree is \df{complete branching} (all vertices are on
539 the same level and internal vertices always have outdegree~2) and that the
540 query paths join a~vertex with one of its ancestors.
542 Koml\'os has given a~simple algorithm that traverses the complete branching
543 tree recursively. At each moment, it maintains an~array of peaks of the restrictions
544 of the query paths to the subtree below the current vertex. If we account for the
545 comparisons performed by this algorithm carefully and express the bound in terms
546 of the size of the original problem (before all the transformations), we get:
548 \thmn{Verification of the MST, Koml\'os \cite{komlos:verify}}\id{verify}%
549 For every weighted graph~$G$ and its spanning tree~$T$, it is sufficient to
550 perform $\O(m)$ comparisons of edge weights to determine whether~$T$ is minimum
551 and to find all $T$-light edges in~$G$.
553 It remains to demonstrate that the overhead of the algorithm needed to find
554 the required comparisons and to infer the peaks from their results can be decreased,
555 so that it gets bounded by the number of comparisons and therefore also by $\O(m)$.
556 We will follow the idea of King from \cite{king:verifytwo}, but as we have the power
557 of the RAM data structures from Section~\ref{ramds} at our command, the low-level
558 details will be easier. Still, the construction is rather technical, so we omit
559 it from this abstract and state only the final theorem:
561 \thmn{Verification of MST on the RAM}\id{ramverify}%
562 There is a~RAM algorithm which for every weighted graph~$G$ and its spanning tree~$T$
563 determines whether~$T$ is minimum and finds all $T$-light edges in~$G$ in time $\O(m)$.
565 \section{A randomized algorithm}\id{randmst}%
567 When we analysed the Contractive Bor\o{u}vka's algorithm in Section~\ref{contalg},
568 we observed that while the number of vertices per iteration decreases exponentially,
569 the number of edges generally does not, so we spend $\Theta(m)$ time on every phase.
570 Karger, Klein and Tarjan \cite{karger:randomized} have overcome this problem by
571 combining the Bor\o{u}vka's algorithm with filtering based on random sampling.
572 This leads to a~randomized algorithm which runs in linear expected time.
574 The principle of the filtering is simple: Let us consider any spanning tree~$T$
575 of the input graph~$G$. Each edge of~$G$ that is $T$-heavy is the heaviest edge
576 of some cycle, so by the Red lemma it cannot participate in
577 the MST of~$G$. We can therefore discard all $T$-heavy edges and continue with
578 finding the MST on the reduced graph. Of course, not all choices of~$T$ are equally
579 good, but it will soon turn out that when we take~$T$ as the MST of a~randomly selected
580 subgraph, only a~small expected number of edges remains:
582 \lemman{Random sampling, Karger \cite{karger:sampling}}\id{samplemma}%
583 Let $H$~be a~subgraph of~$G$ obtained by including each edge independently
584 with probability~$p$. Let further $F$~be the minimum spanning forest of~$H$. Then the
585 expected number of $F$-nonheavy\foot{That is, $F$-light edges and also edges of~$F$ itself.}
586 edges in~$G$ is at most $n/p$.
589 We will formulate the algorithm as a~doubly-recursive procedure. It alternatively
590 performs steps of the Bor\o{u}vka's algorithm and filtering based on the above lemma.
591 The first recursive call computes the MSF of the sampled subgraph, the second one
592 finds the MSF of the original graph, but without the heavy edges.
594 \algn{MSF by random sampling --- the KKT algorithm}\id{kkt}%
596 \algin A~graph $G$ with an~edge comparison oracle.
597 \:Remove isolated vertices from~$G$. If no vertices remain, stop and return an~empty forest.
598 \:Perform two Bor\o{u}vka steps (iterations of Algorithm \ref{contbor}) on~$G$ and
599 remember the set~$B$ of the edges having been contracted.
600 \:Select a~subgraph~$H\subseteq G$ by including each edge independently with
602 \:$F\=\msf(H)$ calculated recursively.
603 \:Construct $G'\subseteq G$ by removing all $F$-heavy edges of~$G$.
604 \:$R\=\msf(G')$ calculated recursively.
606 \algout The minimum spanning forest of~$G$.
609 \>A~careful analysis of this algorithm, based on properties of its recursion tree
610 and on the peak-finding algorithm of the previous section, yields the following time bounds:
613 The KKT algorithm runs in time $\O(\min(n^2,m\log n))$ in the worst case on the RAM.
616 The expected time complexity of the KKT algorithm on the RAM is $\O(m)$.
618 \chapter{Approaching Optimality}\id{optchap}%
620 \section{Soft heaps}\id{shsect}%
622 A~vast majority of MST algorithms that we have encountered so far is based on
623 the Tarjan's Blue rule (Lemma \ref{bluelemma}), the only exception being the
624 randomized KKT algorithm, which also used the Red rule (Lemma \ref{redlemma}). Recently, Chazelle
625 \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann} have presented new
626 deterministic algorithms for the MST which are also based on the combination of
627 both rules. They have reached worst-case time complexity
628 $\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to
629 their results and especially to another algorithm by Pettie and Ramachandran
630 \cite{pettie:optimal} which is provably optimal.
632 At the very heart of all these algorithms lies the \df{soft heap} discovered by
633 Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
634 similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
635 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
636 the expense of \df{corrupting} a~fraction of the inserted elements by raising
637 their values (the values are however never lowered). This allows for
638 a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$.
640 \defnn{Soft heap interface}%
641 The \df{soft heap} contains a~set of distinct items from a~totally ordered universe and it
642 supports the following operations:
644 \:$\<Create>(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$.
645 \:$\<Insert>(H,x)$ --- Insert a~new item~$x$ into the heap~$H$.
646 \:$\<Meld>(P,Q)$ --- Merge two heaps into one, more precisely move all items of a~heap~$Q$
647 to the heap~$P$, destroying~$Q$ in the process. Both heaps must have the same~$\varepsilon$.
648 \:$\<DeleteMin>(H)$ --- Delete the minimum item of the heap~$H$ and return its value
649 (optionally signalling that the value has been corrupted).
650 \:$\<Explode>(H)$ --- Destroy the heap and return a~list of all items contained in it
651 (again optionally marking those corrupted).
654 \>In the thesis, we describe the exact mechanics of the soft heaps and analyse its complexity.
655 The important properties are characterized by the following theorem:
657 \thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
658 A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
659 a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
660 in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
661 heap contains at most $\varepsilon n$ corrupted items.
663 \section{Robust contractions}
665 Having the soft heaps at hand, we would like to use them in a~conventional MST
666 algorithm in place of a~normal heap. The most efficient specimen of a~heap-based
667 algorithm we have seen so far is the Jarn\'\i{}k's algorithm.
668 We can try implanting the soft heap in it, preferably in the earlier
669 version without Fibonacci heaps as the soft heap lacks the \<Decrease> operation.
670 This brave, but somewhat simple-minded attempt is however doomed to
671 fail because of corruption of items inside the soft heap.
672 While the basic structural properties of MST's no longer hold in corrupted graphs,
673 there is a~weaker form of the Contraction lemma that takes the corrupted edges into account.
674 Before we prove this lemma, we expand our awareness of subgraphs which can be contracted.
677 A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,
678 of~$G$'s edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints
679 of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.
681 For example, when we stop the Jarn\'\i{}k's algorithm at some moment and
682 we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.
683 We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
684 of contractible subgraphs:
686 \lemman{Generalized contraction}
687 When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$.
689 We can now bring corruption back to the game and state a~``robust'' version
690 of this lemma. A~notation for corrupted graphs will be handy:
693 When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
694 R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of
695 some of the edges in~$R$.
696 Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with
697 exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$).
699 \lemman{Robust contraction, Chazelle \cite{chazelle:almostacker}}\id{robcont}%
700 Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
701 for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.
704 We will now mimic the Iterated Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
705 of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
706 We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the
707 union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
708 the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
710 \thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
711 Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
712 and~$t$, we can construct a~collection $\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that:
715 \:All the clusters and the set~$R^\C$ are mutually edge-disjoint.
716 \:Each cluster contains at most~$t$ vertices.
717 \:Each vertex of~$G$ is contained in at least one cluster.
718 \:The connected components of the union of all clusters have at least~$t$ vertices each,
719 except perhaps for those which are equal to a~connected component of $G\setminus R^\C$.
720 \:$\vert R^\C\vert \le 2\varepsilon m$.
721 \:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
722 \:The construction takes $\O(n+m\log (1/\varepsilon))$ time.
725 \section{Decision trees}\id{dtsect}%
727 The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
728 trees constructed by brute force for very small subgraphs.
729 Formally, the decision trees are defined as follows:
731 \defnn{Decision trees and their complexity}\id{decdef}%
732 A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
733 are labeled with pairs of $G$'s edges to be compared, each of the two outgoing tree edges
734 corresponds to one possible result of the comparison.
735 Leaves of the tree are labeled with spanning trees of the graph~$G$.
737 A~\df{computation} of the decision tree on a~specific permutation of edge weights
738 in~$G$ is the path from the root to a~leaf such that the outcome of every comparison
739 agrees with the edge weights. The result of the computation is the spanning tree
740 assigned to its final leaf.
741 A~decision tree is \df{correct} iff for every permutation the corresponding
742 computation results in the real MSF of~$G$ with the particular weights.
744 The \df{time complexity} of a~decision tree is defined as its depth. It therefore
745 bounds the number of comparisons spent on every path. (It need not be equal since
746 some paths need not correspond to an~actual computation --- the sequence of outcomes
747 on the path could be unsatisfiable.)
749 A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
750 among the correct decision trees for the given graph.
751 We will denote an~arbitrary optimal decision tree for~$G$ by~${\cal D}(G)$ and its
752 complexity by~$D(G)$.
754 The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~$D(G)$
755 over all graphs~$G$ with $n$~vertices and~$m$ edges.
758 Decision trees are the most general deterministic comparison-based computation model possible.
759 The only operations that count in its time complexity are comparisons. All
760 other computation is free, including solving NP-complete problems or having
761 access to an~unlimited source of non-uniform constants. The decision tree
762 complexity is therefore an~obvious lower bound on the time complexity of the
763 problem in all other comparison-based models.
765 The downside is that we do not know any explicit construction of the optimal
766 decision trees, or at least a~non-constructive proof of their complexity.
767 On the other hand, the complexity of any existing comparison-based algorithm
768 can be used as an~upper bound on the decision tree complexity. Also, we can
769 construct an~optimal decision tree using brute force:
772 An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
773 the Pointer Machine in time $\O(2^{2^{4n^2}})$.
775 \section{An optimal algorithm}\id{optalgsect}%
777 Once we have developed the soft heaps, partitioning and MST decision trees,
778 it is now simple to state the Pettie's and Ramachandran's MST algorithm
779 and prove that it is asymptotically optimal among all MST algorithms in
780 comparison-based models. Several standard MST algorithms from the previous
781 chapters will also play their roles.
782 We will describe the algorithm as a~recursive procedure:
784 \algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
786 \algin A~connected graph~$G$ with an~edge comparison oracle.
787 \:If $G$ has no edges, return an~empty tree.
788 \:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}
789 \:Call the partitioning procedure (\ref{partthm}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
790 a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges.
791 \:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees.
792 \:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph}
793 \:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
794 \:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
795 \:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
796 getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
797 \:$F_C \= \mst(G_C)$ obtained by a~recursive call to this algorithm.
798 \:Return $F_B \cup F_C$.
799 \algout The minimum spanning tree of~$G$.
802 \>Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm})
803 and from the proofs of the respective algorithms used as subroutines. As for time complexity:
806 The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence:
808 T(m,n) \le \sum_i c_1 D(C_i) + T(m/2, n/4) + c_2 m,
810 where~$c_1$ and~$c_2$ are some positive constants and $D$~is the decision tree complexity
811 from the previous section.
813 It turns out that the recurrence is satisfied by the decision tree complexity function
814 $D(m,n)$ itself, so we can prove the following theorem by induction:
817 The time complexity of the Optimal algorithm is $\Theta(D(m,n))$.
819 \paran{Complexity of MST}%
820 As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem
821 is still open and so therefore is the time complexity of the optimal algorithm. However,
822 every time we come up with another comparison-based algorithm, we can use its complexity
823 (or more specifically the number of comparisons it performs, which can be even lower)
824 as an~upper bound on the optimal algorithm.
825 The best explicit comparison-based algorithm known to date has been discovered by Chazelle
826 \cite{chazelle:ackermann} and independently by Pettie \cite{pettie:ackermann}. It achieves complexity $\O(m\timesalpha(m,n))$.
827 Using any of these results, we can prove an~Ackermannian upper bound on the
831 The time complexity of the Optimal algorithm is $\O(m\timesalpha(m,n))$.
833 \chapter{Dynamic Spanning Trees}\id{dynchap}%
835 \section{Dynamic graph algorithms}
837 In many applications, we often need to solve a~certain graph problem for a~sequence of graphs that
838 differ only a~little, so recomputing the solution for every graph from scratch would be a~waste of
839 time. In such cases, we usually turn our attention to \df{dynamic graph algorithms.} A~dynamic
840 algorithm is in fact a~data structure that remembers a~graph. It offers operations that modify the
841 structure of the graph and also operations that query the result of the problem for the current
842 state of the graph. A~typical example of a~problem of this kind is dynamic maintenance of connected
845 \problemn{Dynamic connectivity}
846 Maintain an~undirected graph under a~sequence of the following operations:
848 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
849 The structure could support dynamic addition and removal of vertices, too,
850 but this is easy to add and infrequently used, so we will rather keep the set
851 of vertices fixed for clarity.}
852 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
853 identifier. This assumes that the edge did not exist yet.
854 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
855 \:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
858 In this chapter, we will focus on the dynamic version of the minimum spanning forest.
859 This problem seems to be intimately related to the dynamic connectivity. Indeed, all known
860 algorithms for dynamic connectivity maintain some sort of a~spanning forest.
861 This suggests that a~dynamic MSF algorithm could be obtained by modifying the
862 mechanics of the data structure to keep the forest minimum.
863 We however have to answer one important question first: What should be the output of
864 our MSF data structure? Adding an~operation that returns the MSF of the current
865 graph would be of course possible, but somewhat impractical as this operation would have to
866 spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
867 be making the \<Insert> and \<Delete> operations report the list of modifications
868 of the MSF implied by the change in the graph. It is easy to prove that $\O(1)$
869 modifications always suffice, so we can formulate our problem as follows:
871 \problemn{Dynamic minimum spanning forest}
872 Maintain an~undirected graph with distinct weights on edges (drawn from a~totally ordered set)
873 and its minimum spanning forest under a~sequence of the following operations:
875 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
876 \:$\<Insert>(G,u,v,w)$ --- Insert an~edge $uv$ of weight~$w$ to~$G$. Return its unique
877 identifier and the list of additions and deletions of edges in $\msf(G)$.
878 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
879 Return the list of additions and deletions of edges in $\msf(G)$.
882 \paran{Incremental MSF}%
883 In case only edge insertions are allowed, the problem reduces to finding the heaviest
884 edge (peak) on the tree path covered by the newly inserted edge and replacing the peak
885 if needed. This can be handled quite efficiently by using the Link-Cut trees of Sleator
886 and Tarjan \cite{sleator:trees}. We obtain logarithmic time bound:
888 \thmn{Incremental MSF}
889 When only edge insertions are allowed, the dynamic MSF can be maintained in time $\O(\log n)$
890 amortized per operation.
892 \section{Dynamic connectivity}
894 The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
895 has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and
896 $\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
897 updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
898 were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
899 A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
900 The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
901 de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.
903 The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
904 which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
905 edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
906 Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
907 replacement among the non-tree edges.
909 To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
910 L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
911 of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
912 We will maintain the following \em{invariants:}
915 \def\iinv{{\bo I\the\itemcount~}}
917 \:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
918 if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
919 \:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
920 (This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
925 At the beginning, the graph contains no edges, so both invariants are trivially
926 satisfied. Newly inserted edges enter level~0, which cannot break I1 nor~I2.
928 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
929 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
930 smaller one. We will try to find the replacement edge of the highest possible
931 level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
932 a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According
933 to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
934 at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can move all level~$\ell$
935 edges of~$T_1$ to level~$\ell+1$ without violating either invariant.
937 We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
938 is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
939 whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
940 edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
941 will be the grist for the mill of our amortization argument: We can charge most of the work on level
942 increases and we know that the level of each edge can reach at most~$L$.)
944 If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
945 lower level and so on. If there is no replacement edge at level~0, the tree~$T$
946 remains disconnected.
948 The implementation uses the Eulerian Tour trees of Henzinger and King \cite{henzinger:randdyn}
949 to represent the forests~$F_\ell$ together with the non-tree edges at each particular level.
950 A~simple amortized analysis using the levels yields the following result:
952 \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
953 Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per
954 \<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
958 An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity
959 problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell
960 probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm
961 \cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and
962 $\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims
963 that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations,
964 so it does not fit the definition of the PM we use. The algorithm only does not
965 need direct indexing of arrays.) So far, it is not known how to extend this algorithm
966 to fit our needs, so we omit the details.
968 \section{Dynamic spanning forests}\id{dynmstsect}%
970 Let us turn our attention back to the dynamic MSF.
971 Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
972 algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
973 have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
974 operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved
975 the decremental version of the problem first (which starts with a~given graph and only edge deletions
976 are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
977 We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
978 the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
979 in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
981 \paran{Decremental MSF}%
982 Turning the algorithm from the previous section to the decremental MSF requires only two
983 changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
984 graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
985 MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
986 the lightest possible choice. We will therefore use a~weighted version of the ET-trees.
987 We must ensure that the lower levels cannot contain a~lighter replacement edge,
988 but fortunately the light edges tend to ``bubble up'' in the hierarchy of
989 levels. This can be formalized in form of the following invariant:
992 \def\iinv{{\bo I\the\itemcount~}}
995 \:On every cycle, the heaviest edge has the smallest level.
999 \>This immediately implies that we always select the right replacement edge:
1002 Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
1003 edges for~$e$, the lightest one is at the maximum level.
1005 A~brief analysis also shows that the invariant I3 is observed by all operations
1006 on the structure. We can conclude:
1008 \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
1009 When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of
1010 edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then
1011 updated in time $\O(\log^2 n)$ amortized per operation.
1013 \paran{Fully dynamic MSF}%
1014 The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
1015 reduction whose properties are summarized in the following theorem:
1017 \thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
1018 Suppose that we have a~decremental MSF algorithm with the following properties:
1020 \:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
1021 \:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
1023 \>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
1024 with no edges, that performs $m$~insertions and deletions in amortized time:
1026 \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.}
1029 \corn{Fully dynamic MSF}\id{dynmsfcorr}%
1030 There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized
1031 per operation for graphs on $n$~vertices.
1033 \paran{Dynamic MSF with limited edge weights}%
1034 If the set from which the edge weights are drawn is small, we can take a~different
1035 approach. If only two values are allowed, we split the graph to subgraphs $G_1$ and~$G_2$
1036 induced by the edges of the respective weights and we maintain separate connectivity
1037 structures (together with a~spanning tree) for $G_1$ and $G_2 \cup T_1$ (where $T_1$
1038 is a~spanning tree of~$G_1$). We can easily modify the structure for $G_2\cup
1039 T_1$ to prefer the edges of~$T_1$. This ensures that the spanning tree of $G_2\cup T_1$
1040 will be the MST of the whole~$G$.
1042 If there are more possible values, we simply iterate this construction: the $i$-th
1043 structure contains edges of weight~$i$ and the edges of the spanning tree from the
1044 $(i-1)$-th structure. We get:
1046 \thmn{MSF with limited edge weights}
1047 There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
1048 per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.
1050 \section{Almost minimum trees}\id{kbestsect}%
1052 In some situations, finding the single minimum spanning tree is not enough and we are interested
1053 in the $K$~lightest spanning trees, usually for some small value of~$K$. Katoh, Ibaraki
1054 and Mine \cite{katoh:kmin} have given an~algorithm of time complexity $\O(m\log\beta(m,n) + Km)$,
1055 building on the MST algorithm of Gabow et al.~\cite{gabow:mst}.
1056 Subsequently, Eppstein \cite{eppstein:ksmallest} has discovered an~elegant preprocessing step which allows to reduce
1057 the running time to $\O(m\log\beta(m,n) + \min(K^2,Km))$ by eliminating edges
1058 which are either present in all $K$ trees or in none of them.
1059 We will show a~variant of their algorithm based on the MST verification
1060 procedure of Section~\ref{verifysect}.
1062 In this section, we will require the edge weights to be numeric, because
1063 comparisons are certainly not sufficient to determine the second best spanning tree. We will
1064 assume that our computation model is able to add, subtract and compare the edge weights
1067 Let us focus on finding the second lightest spanning tree first.
1069 \paran{Second lightest spanning tree}%
1070 Suppose that we have a~weighted graph~$G$ and a~sequence $T_1,\ldots,T_z$ of all its spanning
1071 trees. Also suppose that the weights of these spanning trees are distinct and that the sequence
1072 is ordered by weight, i.e., $w(T_1) < \ldots < w(T_z)$ and $T_1 = \mst(G)$. Let us observe
1073 that each tree is similar to at least one of its predecessors:
1075 \lemman{Difference lemma}\id{kbl}%
1076 For each $i>1$ there exists $j<i$ such that $T_i$ and~$T_j$ differ by a~single edge exchange.
1079 This lemma implies that the second best spanning tree~$T_2$ differs from~$T_1$ by a~single
1080 edge exchange. It remains to find which exchange it is, but this can be reduced to finding
1081 peaks of the paths covered by the edges outside~$T_1$, which we already are able to solve
1082 efficiently by the methods of Section~\ref{verifysect}. Therefore:
1085 For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find
1086 edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum.
1089 We will call this procedure \df{finding the best exchange in $(H,T)$.}
1092 Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
1094 \paran{Third lightest spanning tree}%
1095 Once we know~$T_1$ and~$T_2$, how to get~$T_3$? According to the Difference lemma, $T_3$~can be
1096 obtained by a~single exchange from either~$T_1$ or~$T_2$. Therefore we need to find the
1097 best exchange for~$T_2$ and the second best exchange for~$T_1$ and use the better of them.
1098 The latter is not easy to find directly, but we can get around it:
1101 The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
1104 \:If $T_3 = T_1-e'+f'$ for $e'\ne e$, then $T_3/e = (T_1/e)-e'+f'$ in~$G_1$.
1105 \:If $T_3 = T_1-e+f'$, then $T_3 = T_2 - f + f'$ in~$G_2$.
1106 \:If $T_3 = T_2-e'+f'$, then this exchange is found in~$G_2$.
1109 \>Thus we can run the previous algorithm for finding the best edge exchange
1110 on both~$G_1$ and~$G_2$ and find~$T_3$ again in time $\O(m)$.
1112 \paran{Further spanning trees}%
1113 The construction of auxiliary graphs can be iterated to obtain $T_1,\ldots,T_K$
1114 for an~arbitrary~$K$. We will build a~\df{meta-tree} of auxiliary graphs. Each node of this meta-tree
1115 carries a~graph and its minimum spanning tree. The root node contains~$(G,T_1)$,
1116 its sons have $(G_1,T_1/e)$ and $(G_2,T_2)$. When $T_3$ is obtained by an~exchange
1117 in one of these sons, we attach two new leaves to that son and we let them carry the two auxiliary
1118 graphs derived by contracting or deleting the exchanged edge. Then we find the best
1119 edge exchanges among all leaves of the new meta-tree and repeat the process. By Observation \ref{tbobs},
1120 each spanning tree of~$G$ is generated exactly once. The Difference lemma guarantees that
1121 the trees are enumerated in the increasing order. So we get:
1124 Given~$G$ and~$T_1$, we can find $T_2,\ldots,T_K$ in time $\O(Km + K\log K)$.
1126 \paran{Invariant edges}%
1127 Our algorithm can be further improved for small values of~$K$ (which seems to be the common
1128 case in most applications) by the reduction of Eppstein \cite{eppstein:ksmallest}.
1129 We will observe that there are many edges of~$T_1$
1130 which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
1131 many edges of $G\setminus T_1$ which are excluded from all those spanning trees.
1132 When we combine this with the previous construction, we get the following theorem:
1134 \thmn{Finding $K$ lightest spanning trees}\id{kbestthm}%
1135 For a~given graph~$G$ with real edge weights and a~positive integer~$K$, the $K$~best spanning trees can be found
1136 in time $\O(m\timesalpha(m,n) + \min(K^2,Km + K\log K))$.
1138 \chapter{Ranking Combinatorial Structures}\id{rankchap}%
1140 \section{Ranking and unranking}\id{ranksect}%
1142 The techniques for building efficient data structures on the RAM, which we have described
1143 in Section~\ref{ramds}, can be also used for a~variety of problems related
1144 to ranking of combinatorial structures. Generally, the problems are stated
1145 in the following way:
1148 Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
1149 $R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
1150 We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ ordered by~$\prec$
1151 and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function} for $C$ and~$\prec$. When the set
1152 and the order are clear from the context, we will use plain~$R(x)$ and $R^{-1}(x)$.
1153 Also, when $\prec$ is defined on a~superset~$C'$ of~$C$, we naturally extend $R_C(x)$
1154 to elements $x\in C'\setminus C$.
1157 Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered
1158 lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that
1159 is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the
1160 notation of Section~\ref{ramds}). Obviously, $R(x)$ is the integer whose binary
1161 representation is the string~$x$.
1163 %--------------------------------------------------------------------------------
1165 \section{Ranking of permutations}
1168 One of the most common ranking problems is ranking of permutations on the set~$[n]=\{1,2,\ldots,n\}$.
1169 This is frequently used to create arrays indexed by permutations: for example in Ruskey's algorithm
1170 for finding Hamilton cycles in Cayley graphs (see~\cite{ruskey:ham} and \cite{ruskey:hce})
1171 or when exploring state spaces of combinatorial puzzles like the Loyd's Fifteen \cite{ss:fifteen}.
1172 Many other applications are surveyed by Critani et al.~\cite{critani:rau} and in
1173 most cases, the time complexity of the whole algorithm is limited by the efficiency
1174 of the (un)ranking functions.
1176 The permutations are usually ranked according to their lexicographic order.
1177 In fact, an~arbitrary order is often sufficient if the ranks are used solely
1178 for indexing of arrays. The lexicographic order however has an~additional advantage
1179 of a~nice structure, which allows various operations on permutations to be
1180 performed directly on their ranks.
1182 Na\"\i{}ve algorithms for lexicographic ranking require time $\Theta(n^2)$ in the
1183 worst case \cite{reingold:catp} and even on average~\cite{liehe:raulow}.
1184 This can be easily improved to $O(n\log n)$ by using either a binary search
1185 tree to calculate inversions, or by a divide-and-conquer technique, or by clever
1186 use of modular arithmetic (all three algorithms are described in Knuth
1187 \cite{knuth:sas}). Myrvold and Ruskey \cite{myrvold:rank} mention further
1188 improvements to $O(n\log n/\log \log n)$ by using the RAM data structures of Dietz
1191 Linear time complexity was reached by Myrvold and Ruskey \cite{myrvold:rank}
1192 for a~non-lexicographic order, which is defined locally by the history of the
1193 data structure --- in fact, they introduce a linear-time unranking algorithm
1194 first and then they derive an inverse algorithm without describing the order
1195 explicitly. However, they leave the problem of lexicographic ranking open.
1197 We will describe a~general procedure which, when combined with suitable
1198 RAM data structures, yields a~linear-time algorithm for lexicographic
1202 We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
1203 (in other words, arrays) containing every element of~$A$ exactly once. We will
1204 use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$,
1205 and sub-tuples: $\pi[i\ldots j] = (\pi[i],\pi[i+1],\ldots,\pi[j])$.
1206 The lexicographic ranking and unranking functions for the permutations on~$A$
1207 will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively.
1210 Let us first observe that permutations have a simple recursive structure.
1211 If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, the
1212 elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
1213 The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
1214 by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
1215 by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots n]$.
1216 Moreover, when we fix $\pi[1]$, all permutations on the smaller set occur exactly
1217 once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
1220 This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)rank\-ing
1221 of permutations on a $(n-1)$-element set, which suggests a straightforward
1222 algorithm, but unfortunately this set is different from $[n-1]$ and it even
1223 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
1224 but it would require linear time per iteration. To avoid this, we generalize the
1225 problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set
1226 $A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula:
1228 L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! +
1229 L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}),
1231 which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately
1232 translates to the following recursive algorithms for both ranking and unranking
1233 (described for example in \cite{knuth:sas}):
1235 \alg $\<Rank>(\pi,i,n,A)$: Compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
1238 \:If $i\ge n$, return~0.
1240 \:$b\=\<Rank>(\pi,i+1,n,A \setminus \{\pi[i]\})$.
1241 \:Return $a\cdot(n-i)! + b$.
1244 \>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
1247 \alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i\ldots n]$ is the $j$-th permutation on~$A$.
1250 \:If $i>n$, return $(0,\ldots,0)$.
1251 \:$x\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
1252 \:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{x\})$.
1257 \>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to calculate $L^{-1}(j,[n])$.
1259 \paran{Representation of sets}%
1260 The most time-consuming parts of the above algorithms are of course operations
1261 on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity
1262 of the whole algorithm is easy to calculate:
1264 \lemma\id{ranklemma}%
1265 Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence
1266 of deletions, which supports ranking and unranking of elements, and that
1267 the time complexity of a~single operation is at most~$t(n)$.
1268 Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$.
1270 If we store~$A$ in an~ordinary array, we have insertion and deletion in constant time,
1271 but ranking and unranking in~$\O(n)$, so $t(n)=\O(n)$ and the algorithm is quadratic.
1272 Binary search trees give $t(n)=\O(\log n)$. The data structure of Dietz \cite{dietz:oal}
1273 improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equivalent
1274 to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$,
1275 the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$.
1277 To obtain linear time complexity, we will make use of the representation of
1278 vectors by integers on the RAM as developed in Section~\ref{ramds}. We observe
1279 that since the words of the RAM need to be able to hold integers as large as~$n!$,
1280 the word size must be at least $\log n! = \Theta(n\log n)$. Therefore the whole
1281 set~$A$ fits in~$\O(1)$ words and we get:
1283 \thmn{Lexicographic ranking of permutations}
1284 When we order the permutations on the set~$[n]$ lexicographically, both ranking
1285 and unranking can be performed on the RAM in time~$\O(n)$.
1287 \paran{The case of $k$-permutations}%
1288 Our algorithm can be also generalized to lexicographic ranking of
1289 \df{$k$-permutations,} that is of ordered $k$-tuples of distinct elements drawn from the set~$[n]$.
1290 There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$
1291 such $k$-permutations and they have a~recursive structure similar to the one of
1293 Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no
1294 longer rely on the same data structure fitting in a constant number of word-sized integers.
1295 For example, if $k=1$, the ranks are $\O(\log n)$-bit numbers, but the data
1296 structure still requires $\Theta(n\log n)$ bits.
1298 We do a minor side step by remembering the complement of~$A$ instead, that is
1299 the set of the at most~$k$ elements we have already seen. We will call this set~$H$
1300 (because it describes the ``holes'' in~$A$). Since $\Omega(k\log n)$ bits are needed
1301 to represent the rank, the vector representation of~$H$ certainly fits in a~constant
1302 number of words. When we translate the operations on~$A$ to operations on~$H$,
1303 again stored as a~vector, we get:
1305 \thmn{Lexicographic ranking of $k$-permutations}
1306 When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both
1307 ranking and unranking can be performed on the RAM in time~$\O(k)$.
1309 \section{Restricted permutations}
1311 Another interesting class of combinatorial objects that can be counted and
1312 ranked are restricted permutations. An~archetypal member of this class are
1313 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
1314 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}
1315 We will present a~general (un)ranking method for any class of restricted
1316 permutations and derive a~linear-time algorithm for the derangements from it.
1319 We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
1320 all~permutations on~$[n]$.
1321 A~\df{restriction graph} is a~bipartite graph~$G$ whose parts are two copies
1322 of the set~$[n]$. A~permutation $\pi\in{\cal P}$ satisfies the restrictions
1323 if $(i,\pi(i))$ is an~edge of~$G$ for every~$i$.
1325 \paran{Equivalent formulations}%
1326 We will follow the path unthreaded by Kaplansky and Riordan
1327 \cite{kaplansky:rooks} and charted by Stanley in \cite{stanley:econe}.
1328 We will relate restricted permutations to placements of non-attacking
1329 rooks on a~hollow chessboard.
1333 \:A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
1334 \:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares \hbox{$T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$. \hskip-4em} %%HACK
1338 The traces of permutations (and thus the permutations themselves) correspond
1339 exactly to placements of $n$ rooks at the board in a~way such that the rooks do
1340 not attack each other (i.e., there is at most one rook in every row and
1341 likewise in every column; as there are $n$~rooks, there must be exactly one of them in
1342 every row and column). When speaking about \df{rook placements,} we will always
1343 mean non-attacking placements.
1345 Restricted permutations then correspond to placements of rooks on a~board with
1346 some of the squares removed. The \df{holes} (missing squares) correspond to the
1347 non-edges of~$G$, so $\pi\in{\cal P}$ satisfies the restrictions iff
1348 $T(\pi)$ avoids the holes.
1350 Placements of~$n$ rooks (and therefore also restricted permutations) can be
1351 also equated with perfect matchings in the restriction graph~$G$. The edges
1352 of the matching correspond to the squares occupied by the rooks, the condition
1353 that no two rooks share a~row nor column translates to the edges not touching
1354 each other, and the use of exactly~$n$ rooks is equivalent to the matching
1357 There is also a~well-known correspondence between the perfect matchings
1358 in a~bipartite graph and non-zero summands in the formula for the permanent
1359 of the bipartite adjacency matrix~$M$ of the graph. This holds because the
1360 non-zero summands are in one-to-one correspondence with the placements
1361 of~$n$ rooks on the corresponding board. The number of restricted
1362 permutations is therefore equal to the permanent of the matrix~$M$.
1364 The diversity of the characterizations of restricted permutations brings
1365 both good and bad news. The good news is that we can use the
1366 plethora of known results on bipartite matchings. Most importantly, we can efficiently
1367 determine whether there exists at least one permutation satisfying a~given set of restrictions:
1370 There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
1371 a~permutation satisfying a~given restriction graph. The $n$ and~$m$ are the number
1372 of vertices and edges of the restriction graph.
1374 The bad news is that computing the permanent is known to be~$\#\rm P$-complete even
1375 for zero-one matrices (as proven by Valiant \cite{valiant:permanent}).
1376 As a~ranking function for a~set of~matchings can be used to count all such
1377 matchings, we obtain the following theorem:
1380 If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
1381 a~set of restrictions which is a~part of the input, then $\rm P=\#P$.
1383 However, the hardness of computing the permanent is the only obstacle.
1384 We show that whenever we are given a~set of restrictions for which
1385 the counting problem is easy (and it is also easy for subgraphs obtained
1386 by deleting vertices), ranking is easy as well. The key will be once again
1387 a~recursive structure, similar to the one we have seen in the case of plain
1388 permutations in \ref{permrec}. We get:
1390 \thmn{Lexicographic ranking of restricted permutations}
1391 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}$
1392 and it is possible to calculate the permanent of~$M'$ in time $\O(t(n))$ for every matrix $M'$
1393 obtained by deletion of rows and columns from~$M_n$. Then there exist algorithms
1394 for ranking and unranking in ${\cal P}_{A,M_n}$ in time $\O(n^4 + n^2\cdot t(n))$
1395 if $M_n$ and an~$n$-element set~$A$ are given as a~part of the input.
1397 Our time bound for ranking of general restricted permutations section is obviously very coarse.
1398 Its main purpose was to demonstrate that many special cases of the ranking problem can be indeed computed in polynomial time.
1399 For most families of restriction matrices, we can do much better. These speedups are hard to state formally
1400 in general (they depend on the structure of the matrices), but we demonstrate them on the
1401 specific case of derangements. We show that each matrix can be sufficiently characterized
1402 by two numbers: the order of the matrix and the number of zeroes in it. We find a~recurrent
1403 formula for the permanent, based on these parameters, which we use to precalculate all
1404 permanents in advance. When we plug it in the general algorithm, we get:
1406 \thmn{Ranking of derangements}%
1407 For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
1408 lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
1410 \schapter{Conclusions}
1412 We have seen the many facets of the minimum spanning tree problem. It has
1413 turned out that while the major question of the existence of a~linear-time
1414 MST algorithm is still open, backing off a~little bit in an~almost arbitrary
1415 direction leads to a~linear solution. This includes classes of graphs with edge
1416 density at least $\lambda_k(n)$ for an~arbitrary fixed~$k$,
1417 minor-closed classes, and graphs whose edge weights are
1418 integers. Using randomness also helps, as does having the edges pre-sorted.
1420 If we do not know anything about the structure of the graph and we are only allowed
1421 to compare the edge weights, we can use the Pettie's MST algorithm.
1422 Its time complexity is guaranteed to be asymptotically optimal,
1423 but we do not know what it really is --- the best what we have is
1424 an~$\O(m\timesalpha(m,n))$ upper bound and the trivial $\Omega(m)$ lower bound.
1426 One thing we however know for sure. The algorithm runs on the weakest of our
1427 computational models ---the Pointer Machine--- and its complexity is linear
1428 in the minimum number of comparisons needed to decide the problem. We therefore
1429 need not worry about the details of computational models, which have contributed
1430 so much to the linear-time algorithms for our special cases. Instead, it is sufficient
1431 to study the complexity of MST decision trees. However, not much is known about these trees so far.
1433 As for the dynamic algorithms, we have an~algorithm which maintains the minimum
1434 spanning forest within poly-logarithmic time per operation.
1435 The optimum complexity is once again undecided --- the known lower bounds are very far
1436 from the upper ones.
1437 The known algorithms run on the Pointer machine and we do not know if using a~stronger
1440 For the ranking problems, the situation is completely different. We have shown
1441 linear-time algorithms for three important problems of this kind. The techniques,
1442 which we have used, seem to be applicable to other ranking problems. On the other
1443 hand, ranking of general restricted permutations has turned out to balance on the
1444 verge of $\#{\rm P}$-completeness. All our algorithms run
1445 on the RAM model, which seems to be the only sensible choice for problems of
1446 inherently arithmetic nature. While the unit-cost assumption on arithmetic operations
1447 is not universally accepted, our results imply that the complexity of our algorithm
1448 is dominated by the necessary arithmetics.
1450 Aside from the concrete problems we have solved, we have also built several algorithmic
1451 techniques of general interest: the unification procedures using pointer-based
1452 bucket sorting and the vector computations on the RAM. We hope that they will
1453 be useful in many other algorithms.
1455 \schapter{Bibliography}
1460 \ifodd\pageno\else\hbox{}\fi