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