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. This improves the time complexity
481 The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time
482 $\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i \mid \log^{(i)}n \le m/n \}$.
485 The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
487 \paran{Integer weights}%
488 The algorithm spends most of the time in phases which have small heaps. Once the
489 heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
490 to guarantee that at most~$k$ phases remain. This means that if we are able to
491 construct a~heap of size $\Omega(\log^{(k)} n)$ with constant time per operation,
492 we can get a~linear-time algorithm for MST. This is the case when the weights are
493 integers (we can use the Q-heap trees from Section~\ref{ramds}).
495 \thmn{MST for integer weights, Fredman and Willard \cite{fw:transdich}}\id{intmst}%
496 MST of a~graph with integer edge weights can be found in time $\O(m)$ on the Word-RAM.
498 \section{Verification of minimality}\id{verifysect}%
500 Now we will turn our attention to a~slightly different problem: given a~spanning
501 tree, how to verify that it is minimum? We will show that this can be achieved
502 in linear time and it will serve as a~basis for a~randomized linear-time
503 MST algorithm in the next section.
505 MST verification has been studied by Koml\'os \cite{komlos:verify}, who has
506 proven that $\O(m)$ edge comparisons are sufficient, but his algorithm needed
507 super-linear time to find the edges to compare. Dixon, Rauch and Tarjan \cite{dixon:verify}
508 have later shown that the overhead can be reduced
509 to linear time on the RAM using preprocessing and table lookup on small
510 subtrees. Later, King has given a~simpler algorithm in \cite{king:verifytwo}.
512 To verify that a~spanning tree~$T$ is minimum, it is sufficient to check that all
513 edges outside~$T$ are $T$-heavy. For each edge $uv\in E\setminus T$, we will
514 find the heaviest edge of the tree path $T[u,v]$ (we will call it the \df{peak}
515 of the path) and compare its weight to $w(uv)$. We have therefore transformed
516 the MST verification to the problem of finding peaks for a~set of \df{query
517 paths} on a~given tree. By a~sequence of further transformations, we can even
518 assume that the given tree is \df{complete branching} (all vertices are on
519 the same level and internal vertices always have outdegree~2) and that the
520 query paths join a~vertex with one of its ancestors.
522 Koml\'os has given a~simple algorithm that traverses the complete branching
523 tree recursively. At each moment, it maintains an~array of peaks of the restrictions
524 of the query paths to the subtree below the current vertex. If we account for the
525 comparisons performed by this algorithm carefully and express the bound in terms
526 of the size of the original problem (before all the transformations), we get:
528 \thmn{Verification of the MST, Koml\'os \cite{komlos:verify}}\id{verify}%
529 For every weighted graph~$G$ and its spanning tree~$T$, it is sufficient to
530 perform $\O(m)$ comparisons of edge weights to determine whether~$T$ is minimum
531 and to find all $T$-light edges in~$G$.
533 It remains to demonstrate that the overhead of the algorithm needed to find
534 the required comparisons and to infer the peaks from their results can be decreased,
535 so that it gets bounded by the number of comparisons and therefore also by $\O(m)$.
536 We will follow the idea of King from \cite{king:verifytwo}, but as we have the power
537 of the RAM data structures from Section~\ref{ramds} at our command, the low-level
538 details will be easier. Still, the construction is rather technical, so we omit
539 it from this abstract and state only the final theorem:
541 \thmn{Verification of MST on the RAM}\id{ramverify}%
542 There is a~RAM algorithm which for every weighted graph~$G$ and its spanning tree~$T$
543 determines whether~$T$ is minimum and finds all $T$-light edges in~$G$ in time $\O(m)$.
545 \section{A randomized algorithm}\id{randmst}%
547 When we analysed the Contractive Bor\o{u}vka's algorithm in Section~\ref{contalg},
548 we observed that while the number of vertices per iteration decreases exponentially,
549 the number of edges generally does not, so we spend $\Theta(m)$ time on every phase.
550 Karger, Klein and Tarjan \cite{karger:randomized} have overcome this problem by
551 combining the Bor\o{u}vka's algorithm with filtering based on random sampling.
552 This leads to a~randomized algorithm which runs in linear expected time.
554 The principle of the filtering is simple: Let us consider any spanning tree~$T$
555 of the input graph~$G$. Each edge of~$G$ that is $T$-heavy is the heaviest edge
556 of some cycle, so by the Red lemma it cannot participate in
557 the MST of~$G$. We can therefore discard all $T$-heavy edges and continue with
558 finding the MST on the reduced graph. Of course, not all choices of~$T$ are equally
559 good, but it will soon turn out that when we take~$T$ as the MST of a~randomly selected
560 subgraph, only a~small expected number of edges remains:
562 \lemman{Random sampling, Karger \cite{karger:sampling}}\id{samplemma}%
563 Let $H$~be a~subgraph of~$G$ obtained by including each edge independently
564 with probability~$p$. Let further $F$~be the minimum spanning forest of~$H$. Then the
565 expected number of $F$-nonheavy\foot{That is, $F$-light edges and also edges of~$F$ itself.}
566 edges in~$G$ is at most $n/p$.
569 We will formulate the algorithm as a~doubly-recursive procedure. It alternatively
570 performs steps of the Bor\o{u}vka's algorithm and filtering based on the above lemma.
571 The first recursive call computes the MSF of the sampled subgraph, the second one
572 finds the MSF of the original graph, but without the heavy edges.
574 \algn{MSF by random sampling --- the KKT algorithm}\id{kkt}%
576 \algin A~graph $G$ with an~edge comparison oracle.
577 \:Remove isolated vertices from~$G$. If no vertices remain, stop and return an~empty forest.
578 \:Perform two Bor\o{u}vka steps (iterations of Algorithm \ref{contbor}) on~$G$ and
579 remember the set~$B$ of the edges having been contracted.
580 \:Select a~subgraph~$H\subseteq G$ by including each edge independently with
582 \:$F\=\msf(H)$ calculated recursively.
583 \:Construct $G'\subseteq G$ by removing all $F$-heavy edges of~$G$.
584 \:$R\=\msf(G')$ calculated recursively.
586 \algout The minimum spanning forest of~$G$.
589 \>A~careful analysis of this algorithm, based on properties of its recursion tree
590 and on the peak-finding algorithm of the previous section, yields the following time bounds:
593 The KKT algorithm runs in time $\O(\min(n^2,m\log n))$ in the worst case on the RAM.
594 The expected time complexity is $\O(m)$.
596 \chapter{Approaching Optimality}\id{optchap}%
598 \section{Soft heaps}\id{shsect}%
600 A~vast majority of MST algorithms that we have encountered so far is based on
601 the Tarjan's Blue rule (Lemma \ref{bluelemma}), the only exception being the
602 randomized KKT algorithm, which also used the Red rule (Lemma \ref{redlemma}). Recently, Chazelle
603 \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann} have presented new
604 deterministic algorithms for the MST which are also based on the combination of
605 both rules. They have reached worst-case time complexity
606 $\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to
607 their results and especially to another algorithm by Pettie and Ramachandran
608 \cite{pettie:optimal} which is provably optimal.
610 At the very heart of all these algorithms lies the \df{soft heap} discovered by
611 Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
612 similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
613 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
614 the expense of \df{corrupting} a~fraction of the inserted elements by raising
615 their values (the values are however never lowered). This allows for
616 a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$.
618 \>In the thesis, we describe the exact mechanics of the soft heaps and analyse its complexity.
619 The important properties are characterized by the following theorem:
621 \thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
622 A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
623 a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
624 in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the
625 heap contains at most $\varepsilon n$ corrupted items.
627 \section{Robust contractions}
629 Having the soft heaps at hand, we would like to use them in a~conventional MST
630 algorithm in place of a~normal heap. We can for example try implanting the soft heap
631 in the Jarn\'i{}k's algorithm, preferably in the earlier
632 version without Fibonacci heaps as the soft heaps lack the \<Decrease> operation.
633 This brave, but somewhat simple-minded attempt is however doomed to
634 fail because of corruption of items inside the soft heap.
635 While the basic structural properties of MST's no longer hold in corrupted graphs,
636 there is a~weaker form of the Contraction lemma that takes the corrupted edges into account.
637 Before we prove this lemma, we expand our awareness of subgraphs which can be contracted.
640 A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is,
641 of~$G$'s edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints
642 of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$.
644 For example, when we stop the Jarn\'\i{}k's algorithm at some moment and
645 we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible.
646 We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language
647 of contractible subgraphs:
649 \lemman{Generalized contraction}
650 When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$.
652 Let us bring corruption back to the game and state a~``robust'' version
656 When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt
657 R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of
658 some of the edges in~$R$.
659 Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with
660 exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$).
662 \lemman{Robust contraction, Chazelle \cite{chazelle:almostacker}}\id{robcont}%
663 Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$
664 for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R^C) \cup R^C$.
667 We will now mimic the Iterated Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
668 of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
669 We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the
670 union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
671 the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
673 \thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
674 Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
675 and~$t$, we can construct a~collection $\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that:
678 \:All the clusters and the set~$R^\C$ are mutually edge-disjoint.
679 \:Each cluster contains at most~$t$ vertices.
680 \:Each vertex of~$G$ is contained in at least one cluster.
681 \:The connected components of the union of all clusters have at least~$t$ vertices each,
682 except perhaps for those which are equal to a~connected component of $G\setminus R^\C$.
683 \:$\vert R^\C\vert \le 2\varepsilon m$.
684 \:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$.
685 \:The construction takes $\O(n+m\log (1/\varepsilon))$ time.
688 \section{Decision trees}\id{dtsect}%
690 The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
691 trees constructed by brute force for very small subgraphs.
692 Formally, the decision trees are defined as follows:
694 \defnn{Decision trees and their complexity}\id{decdef}%
695 A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
696 are labeled with pairs of $G$'s edges to be compared, each of the two outgoing tree edges
697 corresponds to one possible result of the comparison.
698 Leaves of the tree are labeled with spanning trees of the graph~$G$.
700 A~\df{computation} of the decision tree on a~specific permutation of edge weights
701 in~$G$ is the path from the root to a~leaf such that the outcome of every comparison
702 agrees with the edge weights. The result of the computation is the spanning tree
703 assigned to its final leaf.
704 A~decision tree is \df{correct} iff for every permutation the corresponding
705 computation results in the real MSF of~$G$ with the particular weights.
707 The \df{time complexity} of a~decision tree is defined as its depth. It therefore
708 bounds the number of comparisons spent on every path. (It need not be equal since
709 some paths need not correspond to an~actual computation --- the sequence of outcomes
710 on the path could be unsatisfiable.)
712 A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
713 among the correct decision trees for the given graph.
714 We will denote an~arbitrary optimal decision tree for~$G$ by~${\cal D}(G)$ and its
715 complexity by~$D(G)$.
717 The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~$D(G)$
718 over all graphs~$G$ with $n$~vertices and~$m$ edges.
721 Decision trees are the most general deterministic comparison-based computation model possible.
722 The only operations that count in its time complexity are comparisons. All
723 other computation is free, including solving NP-complete problems or having
724 access to an~unlimited source of non-uniform constants. The decision tree
725 complexity is therefore an~obvious lower bound on the time complexity of the
726 problem in all other comparison-based models.
728 The downside is that we do not know any explicit construction of the optimal
729 decision trees, or at least a~non-constructive proof of their complexity.
730 On the other hand, the complexity of any existing comparison-based algorithm
731 can be used as an~upper bound on the decision tree complexity. Also, we can
732 construct an~optimal decision tree using brute force:
735 An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on
736 the Pointer Machine in time $\O(2^{2^{4n^2}})$.
738 \section{An optimal algorithm}\id{optalgsect}%
740 Once we have developed the soft heaps, partitioning and MST decision trees,
741 it is now simple to state the Pettie's and Ramachandran's MST algorithm
742 and prove that it is asymptotically optimal among all MST algorithms in
743 comparison-based models. Several standard MST algorithms from the previous
744 chapters will also play their roles.
745 We will describe the algorithm as a~recursive procedure:
747 \algn{Optimal MST algorithm, Pettie and Ramachandran \cite{pettie:optimal}}\id{optimal}%
749 \algin A~connected graph~$G$ with an~edge comparison oracle.
750 \:If $G$ has no edges, return an~empty tree.
751 \:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters}
752 \:Call the partitioning procedure (\ref{partthm}) on $G$ and $t$ with $\varepsilon=1/8$. It returns
753 a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges.
754 \:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees.
755 \:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph}
756 \:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
757 \:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
758 \:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
759 getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
760 \:$F_C \= \mst(G_C)$ obtained by a~recursive call to this algorithm.
761 \:Return $F_B \cup F_C$.
762 \algout The minimum spanning tree of~$G$.
765 \>Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm})
766 and from the proofs of the respective algorithms used as subroutines. As for time complexity, we prove:
769 The time complexity of the Optimal algorithm is $\Theta(D(m,n))$.
771 \paran{Complexity of MST}%
772 As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem
773 is still open and so therefore is the time complexity of the optimal algorithm. However,
774 every time we come up with another comparison-based algorithm, we can use its complexity
775 (or more specifically the number of comparisons it performs, which can be even lower)
776 as an~upper bound on the optimal algorithm.
777 The best explicit comparison-based algorithm known to date has been discovered by Chazelle
778 \cite{chazelle:ackermann} and independently by Pettie \cite{pettie:ackermann}. It achieves complexity $\O(m\timesalpha(m,n))$.
779 Using any of these results, we can prove an~Ackermannian upper bound on the
783 The time complexity of the Optimal algorithm is $\O(m\timesalpha(m,n))$.
785 \chapter{Dynamic Spanning Trees}\id{dynchap}%
787 \section{Dynamic graph algorithms}
789 In many applications, we often need to solve a~certain graph problem for a~sequence of graphs that
790 differ only a~little, so recomputing the solution for every graph from scratch would be a~waste of
791 time. In such cases, we usually turn our attention to \df{dynamic graph algorithms.} A~dynamic
792 algorithm is in fact a~data structure that remembers a~graph. It offers operations that modify the
793 structure of the graph and also operations that query the result of the problem for the current
794 state of the graph. A~typical example of a~problem of this kind is dynamic maintenance of connected
797 \problemn{Dynamic connectivity}
798 Maintain an~undirected graph under a~sequence of the following operations:
800 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
801 The structure could support dynamic addition and removal of vertices, too,
802 but this is easy to add and infrequently used, so we will rather keep the set
803 of vertices fixed for clarity.}
804 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
805 identifier. This assumes that the edge did not exist yet.
806 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
807 \:$\<Connected>(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$.
810 In this chapter, we will focus on the dynamic version of the minimum spanning forest.
811 This problem seems to be intimately related to the dynamic connectivity. Indeed, all known
812 algorithms for dynamic connectivity maintain some sort of a~spanning forest.
813 This suggests that a~dynamic MSF algorithm could be obtained by modifying the
814 mechanics of the data structure to keep the forest minimum.
815 We however have to answer one important question first: What should be the output of
816 our MSF data structure? Adding an~operation that returns the MSF of the current
817 graph would be of course possible, but somewhat impractical as this operation would have to
818 spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
819 be making the \<Insert> and \<Delete> operations report the list of modifications
820 of the MSF implied by the change in the graph. It is easy to prove that $\O(1)$
821 modifications always suffice, so we can formulate our problem as follows:
823 \problemn{Dynamic minimum spanning forest}
824 Maintain an~undirected graph with distinct weights on edges (drawn from a~totally ordered set)
825 and its minimum spanning forest under a~sequence of the following operations:
827 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
828 \:$\<Insert>(G,u,v,w)$ --- Insert an~edge $uv$ of weight~$w$ to~$G$. Return its unique
829 identifier and the list of additions and deletions of edges in $\msf(G)$.
830 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
831 Return the list of additions and deletions of edges in $\msf(G)$.
834 \paran{Incremental MSF}%
835 In case only edge insertions are allowed, the problem reduces to finding the heaviest
836 edge (peak) on the tree path covered by the newly inserted edge and replacing the peak
837 if needed. This can be handled quite efficiently by using the Link-Cut trees of Sleator
838 and Tarjan \cite{sleator:trees}. We obtain logarithmic time bound:
840 \thmn{Incremental MSF}
841 When only edge insertions are allowed, the dynamic MSF can be maintained in time $\O(\log n)$
842 amortized per operation.
844 \section{Dynamic connectivity}
846 The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic}
847 has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and
848 $\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the
849 updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$
850 were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}.
851 A~polylogarithmic time bound was first reached by the randomized algorithm of Henzinger and King \cite{henzinger:randdyn}.
852 The best result known as of now is the $\O(\log^2 n)$ time deterministic algorithm by Holm,
853 de~Lichtenberg and Thorup \cite{holm:polylog}, which will we describe in this section.
855 The algorithm will maintain a~spanning forest~$F$ of the current graph~$G$, represented by an~ET-tree
856 which will be used to answer connectivity queries. The edges of~$G\setminus F$ will be stored as~non-tree
857 edges in the ET-tree. Hence, an~insertion of an~edge to~$G$ either adds it to~$F$ or inserts it as non-tree.
858 Deletions of non-tree edges are also easy, but when a~tree edge is deleted, we have to search for its
859 replacement among the non-tree edges.
861 To govern the search in an~efficient way, we will associate each edge~$e$ with a~level $\ell(e) \le
862 L = \lfloor\log_2 n\rfloor$. For each level~$i$, we will use~$F_i$ to denote the subforest
863 of~$F$ containing edges of level at least~$i$. Therefore $F=F_0 \supseteq F_1 \supseteq \ldots \supseteq F_L$.
864 We will maintain the following \em{invariants:}
867 \def\iinv{{\bo I\the\itemcount~}}
869 \:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
870 if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
871 \:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
872 (This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
877 At the beginning, the graph contains no edges, so both invariants are trivially
878 satisfied. Newly inserted edges enter level~0, which cannot break I1 nor~I2.
880 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
881 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
882 smaller one. We will try to find the replacement edge of the highest possible
883 level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
884 a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According
885 to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
886 at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can move all level~$\ell$
887 edges of~$T_1$ to level~$\ell+1$ without violating either invariant.
889 We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
890 is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
891 whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
892 edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
893 will be the grist for the mill of our amortization argument: We can charge most of the work on level
894 increases and we know that the level of each edge can reach at most~$L$.)
896 If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
897 lower level and so on. If there is no replacement edge at level~0, the tree~$T$
898 remains disconnected.
900 The implementation uses the Eulerian Tour trees of Henzinger and King \cite{henzinger:randdyn}
901 to represent the forests~$F_\ell$ together with the non-tree edges at each particular level.
902 A~simple amortized analysis using the levels yields the following result:
904 \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
905 Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per
906 \<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
910 An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity
911 problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell
912 probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm
913 \cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and
914 $\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims
915 that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations,
916 so it does not fit the definition of the PM we use. The algorithm only does not
917 need direct indexing of arrays.) So far, it is not known how to extend this algorithm
918 to fit our needs, so we omit the details.
920 \section{Dynamic spanning forests}\id{dynmstsect}%
922 Let us turn our attention back to the dynamic MSF.
923 Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
924 algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
925 have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
926 operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved
927 the decremental version of the problem first (which starts with a~given graph and only edge deletions
928 are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
929 We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
930 the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
931 in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
933 \paran{Decremental MSF}%
934 Turning the algorithm from the previous section to the decremental MSF requires only two
935 changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
936 graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
937 MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
938 the lightest possible choice. We will therefore use a~weighted version of the ET-trees.
939 We must ensure that the lower levels cannot contain a~lighter replacement edge,
940 but fortunately the light edges tend to ``bubble up'' in the hierarchy of
941 levels. This can be formalized in form of the following invariant:
944 \def\iinv{{\bo I\the\itemcount~}}
947 \:On every cycle, the heaviest edge has the smallest level.
951 \>This immediately implies that we always select the right replacement edge:
954 Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
955 edges for~$e$, the lightest one is at the maximum level.
957 A~brief analysis also shows that the invariant I3 is observed by all operations
958 on the structure. We can conclude:
960 \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
961 When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of
962 edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then
963 updated in time $\O(\log^2 n)$ amortized per operation.
965 \paran{Fully dynamic MSF}%
966 The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
967 reduction whose properties are summarized in the following theorem:
969 \thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
970 Suppose that we have a~decremental MSF algorithm with the following properties:
972 \:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
973 \:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
975 \>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
976 with no edges, that performs $m$~insertions and deletions in amortized time:
978 \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.}
981 \corn{Fully dynamic MSF}\id{dynmsfcorr}%
982 There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized
983 per operation for graphs on $n$~vertices.
985 \paran{Dynamic MSF with limited edge weights}%
986 If the set from which the edge weights are drawn is small, we can take a~different
987 approach. If only two values are allowed, we split the graph to subgraphs $G_1$ and~$G_2$
988 induced by the edges of the respective weights and we maintain separate connectivity
989 structures (together with a~spanning tree) for $G_1$ and $G_2 \cup T_1$ (where $T_1$
990 is a~spanning tree of~$G_1$). We can easily modify the structure for $G_2\cup
991 T_1$ to prefer the edges of~$T_1$. This ensures that the spanning tree of $G_2\cup T_1$
992 will be the MST of the whole~$G$.
994 If there are more possible values, we simply iterate this construction: the $i$-th
995 structure contains edges of weight~$i$ and the edges of the spanning tree from the
996 $(i-1)$-th structure. We get:
998 \thmn{MSF with limited edge weights}
999 There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
1000 per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.
1002 \section{Almost minimum trees}\id{kbestsect}%
1004 In some situations, finding the single minimum spanning tree is not enough and we are interested
1005 in the $K$~lightest spanning trees, usually for some small value of~$K$. Katoh, Ibaraki
1006 and Mine \cite{katoh:kmin} have given an~algorithm of time complexity $\O(m\log\beta(m,n) + Km)$,
1007 building on the MST algorithm of Gabow et al.~\cite{gabow:mst}.
1008 Subsequently, Eppstein \cite{eppstein:ksmallest} has discovered an~elegant preprocessing step which allows to reduce
1009 the running time to $\O(m\log\beta(m,n) + \min(K^2,Km))$ by eliminating edges
1010 which are either present in all $K$ trees or in none of them.
1011 We will show a~variant of their algorithm based on the MST verification
1012 procedure of Section~\ref{verifysect}.
1014 In this section, we will require the edge weights to be numeric, because
1015 comparisons are certainly not sufficient to determine the second best spanning tree. We will
1016 assume that our computation model is able to add, subtract and compare the edge weights
1019 Let us focus on finding the second lightest spanning tree first.
1021 \paran{Second lightest spanning tree}%
1022 Suppose that we have a~weighted graph~$G$ and a~sequence $T_1,\ldots,T_z$ of all its spanning
1023 trees. Also suppose that the weights of these spanning trees are distinct and that the sequence
1024 is ordered by weight, i.e., $w(T_1) < \ldots < w(T_z)$ and $T_1 = \mst(G)$. Let us observe
1025 that each tree is similar to at least one of its predecessors:
1027 \lemman{Difference lemma}\id{kbl}%
1028 For each $i>1$ there exists $j<i$ such that $T_i$ and~$T_j$ differ by a~single edge exchange.
1031 This lemma implies that the second best spanning tree~$T_2$ differs from~$T_1$ by a~single
1032 edge exchange. It remains to find which exchange it is, but this can be reduced to finding
1033 peaks of the paths covered by the edges outside~$T_1$, which we already are able to solve
1034 efficiently by the methods of Section~\ref{verifysect}. Therefore:
1037 For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find
1038 edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum.
1041 We will call this procedure \df{finding the best exchange in $(H,T)$.}
1044 Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$.
1046 \paran{Third lightest spanning tree}%
1047 Once we know~$T_1$ and~$T_2$, how to get~$T_3$? According to the Difference lemma, $T_3$~can be
1048 obtained by a~single exchange from either~$T_1$ or~$T_2$. Therefore we need to find the
1049 best exchange for~$T_2$ and the second best exchange for~$T_1$ and use the better of them.
1050 The latter is not easy to find directly, but we can get around it:
1053 The tree $T_3$~can be obtained by a~single edge exchange in either $(G_1,T_1/e)$ or $(G_2,T_2)$:
1056 \:If $T_3 = T_1-e'+f'$ for $e'\ne e$, then $T_3/e = (T_1/e)-e'+f'$ in~$G_1$.
1057 \:If $T_3 = T_1-e+f'$, then $T_3 = T_2 - f + f'$ in~$G_2$.
1058 \:If $T_3 = T_2-e'+f'$, then this exchange is found in~$G_2$.
1061 \>Thus we can run the previous algorithm for finding the best edge exchange
1062 on both~$G_1$ and~$G_2$ and find~$T_3$ again in time $\O(m)$.
1064 \paran{Further spanning trees}%
1065 The construction of auxiliary graphs can be iterated to obtain $T_1,\ldots,T_K$
1066 for an~arbitrary~$K$. We will build a~\df{meta-tree} of auxiliary graphs. Each node of this meta-tree
1067 carries a~graph and its minimum spanning tree. The root node contains~$(G,T_1)$,
1068 its sons have $(G_1,T_1/e)$ and $(G_2,T_2)$. When $T_3$ is obtained by an~exchange
1069 in one of these sons, we attach two new leaves to that son and we let them carry the two auxiliary
1070 graphs derived by contracting or deleting the exchanged edge. Then we find the best
1071 edge exchanges among all leaves of the new meta-tree and repeat the process. By Observation \ref{tbobs},
1072 each spanning tree of~$G$ is generated exactly once. The Difference lemma guarantees that
1073 the trees are enumerated in the increasing order. So we get:
1076 Given~$G$ and~$T_1$, we can find $T_2,\ldots,T_K$ in time $\O(Km + K\log K)$.
1078 \paran{Invariant edges}%
1079 Our algorithm can be further improved for small values of~$K$ (which seems to be the common
1080 case in most applications) by the reduction of Eppstein \cite{eppstein:ksmallest}.
1081 We will observe that there are many edges of~$T_1$
1082 which are guaranteed to be contained in $T_2,\ldots,T_K$ as well, and likewise there are
1083 many edges of $G\setminus T_1$ which are excluded from all those spanning trees.
1084 When we combine this with the previous construction, we get the following theorem:
1086 \thmn{Finding $K$ lightest spanning trees}\id{kbestthm}%
1087 For a~given graph~$G$ with real edge weights and a~positive integer~$K$, the $K$~best spanning trees can be found
1088 in time $\O(m\timesalpha(m,n) + \min(K^2,Km + K\log K))$.
1090 \chapter{Ranking Combinatorial Structures}\id{rankchap}%
1092 \section{Ranking and unranking}\id{ranksect}%
1094 The techniques for building efficient data structures on the RAM, which we have described
1095 in Section~\ref{ramds}, can be also used for a~variety of problems related
1096 to ranking of combinatorial structures. Generally, the problems are stated
1097 in the following way:
1100 Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
1101 $R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
1102 We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ ordered by~$\prec$
1103 and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function} for $C$ and~$\prec$. When the set
1104 and the order are clear from the context, we will use plain~$R(x)$ and $R^{-1}(x)$.
1105 Also, when $\prec$ is defined on a~superset~$C'$ of~$C$, we naturally extend $R_C(x)$
1106 to elements $x\in C'\setminus C$.
1109 Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered
1110 lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that
1111 is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the
1112 notation of Section~\ref{ramds}). Obviously, $R(x)$ is the integer whose binary
1113 representation is the string~$x$.
1115 %--------------------------------------------------------------------------------
1117 \section{Ranking of permutations}
1120 One of the most common ranking problems is ranking of permutations on the set~$[n]=\{1,2,\ldots,n\}$.
1121 This is frequently used to create arrays indexed by permutations: for example in Ruskey's algorithm
1122 for finding Hamilton cycles in Cayley graphs (see~\cite{ruskey:ham} and \cite{ruskey:hce})
1123 or when exploring state spaces of combinatorial puzzles like the Loyd's Fifteen \cite{ss:fifteen}.
1124 Many other applications are surveyed by Critani et al.~\cite{critani:rau} and in
1125 most cases, the time complexity of the whole algorithm is limited by the efficiency
1126 of the (un)ranking functions.
1128 The permutations are usually ranked according to their lexicographic order.
1129 In fact, an~arbitrary order is often sufficient if the ranks are used solely
1130 for indexing of arrays. The lexicographic order however has an~additional advantage
1131 of a~nice structure, which allows various operations on permutations to be
1132 performed directly on their ranks.
1134 Na\"\i{}ve algorithms for lexicographic ranking require time $\Theta(n^2)$ in the
1135 worst case \cite{reingold:catp} and even on average~\cite{liehe:raulow}.
1136 This can be easily improved to $O(n\log n)$ by using either a binary search
1137 tree to calculate inversions, or by a divide-and-conquer technique, or by clever
1138 use of modular arithmetic (all three algorithms are described in Knuth
1139 \cite{knuth:sas}). Myrvold and Ruskey \cite{myrvold:rank} mention further
1140 improvements to $O(n\log n/\log \log n)$ by using the RAM data structures of Dietz
1143 Linear time complexity was reached by Myrvold and Ruskey \cite{myrvold:rank}
1144 for a~non-lexicographic order, which is defined locally by the history of the
1145 data structure --- in fact, they introduce a linear-time unranking algorithm
1146 first and then they derive an inverse algorithm without describing the order
1147 explicitly. However, they leave the problem of lexicographic ranking open.
1149 We will describe a~general procedure which, when combined with suitable
1150 RAM data structures, yields a~linear-time algorithm for lexicographic
1154 We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
1155 (in other words, arrays) containing every element of~$A$ exactly once. We will
1156 use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$,
1157 and sub-tuples: $\pi[i\ldots j] = (\pi[i],\pi[i+1],\ldots,\pi[j])$.
1158 The lexicographic ranking and unranking functions for the permutations on~$A$
1159 will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively.
1162 Let us first observe that permutations have a simple recursive structure.
1163 If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, the
1164 elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
1165 The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
1166 by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
1167 by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots n]$.
1168 Moreover, when we fix $\pi[1]$, all permutations on the smaller set occur exactly
1169 once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
1172 This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)rank\-ing
1173 of permutations on a $(n-1)$-element set, which suggests a straightforward
1174 algorithm, but unfortunately this set is different from $[n-1]$ and it even
1175 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
1176 but it would require linear time per iteration. To avoid this, we generalize the
1177 problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set
1178 $A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula:
1180 L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! +
1181 L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}),
1183 which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately
1184 translates to the following recursive algorithms for both ranking and unranking
1185 (described for example in \cite{knuth:sas}):
1187 \alg $\<Rank>(\pi,i,n,A)$: Compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
1190 \:If $i\ge n$, return~0.
1192 \:$b\=\<Rank>(\pi,i+1,n,A \setminus \{\pi[i]\})$.
1193 \:Return $a\cdot(n-i)! + b$.
1196 \>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
1199 \alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i\ldots n]$ is the $j$-th permutation on~$A$.
1202 \:If $i>n$, return $(0,\ldots,0)$.
1203 \:$x\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
1204 \:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{x\})$.
1209 \>We can call $\<Unrank>(j,1,n,[n])$ to calculate $L^{-1}(j,[n])$.
1211 \paran{Representation of sets}%
1212 The most time-consuming parts of the above algorithms are of course operations
1213 on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity
1214 of the whole algorithm is easy to calculate:
1216 \lemma\id{ranklemma}%
1217 Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence
1218 of deletions, which supports ranking and unranking of elements, and that
1219 the time complexity of a~single operation is at most~$t(n)$.
1220 Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$.
1222 If we store~$A$ in an~ordinary array, we have insertion and deletion in constant time,
1223 but ranking and unranking in~$\O(n)$, so $t(n)=\O(n)$ and the algorithm is quadratic.
1224 Binary search trees give $t(n)=\O(\log n)$. The data structure of Dietz \cite{dietz:oal}
1225 improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equivalent
1226 to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$,
1227 the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$.
1229 To obtain linear time complexity, we will make use of the representation of
1230 vectors by integers on the RAM as developed in Section~\ref{ramds}. We observe
1231 that since the words of the RAM need to be able to hold integers as large as~$n!$,
1232 the word size must be at least $\log n! = \Theta(n\log n)$. Therefore the whole
1233 set~$A$ fits in~$\O(1)$ words and we get:
1235 \thmn{Lexicographic ranking of permutations}
1236 When we order the permutations on the set~$[n]$ lexicographically, both ranking
1237 and unranking can be performed on the RAM in time~$\O(n)$.
1239 \paran{The case of $k$-permutations}%
1240 Our algorithm can be also generalized to lexicographic ranking of
1241 \df{$k$-permutations,} that is of ordered $k$-tuples of distinct elements drawn from the set~$[n]$.
1242 There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$
1243 such $k$-permutations and they have a~recursive structure similar to the one of
1245 Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no
1246 longer rely on the same data structure fitting in a constant number of word-sized integers.
1247 For example, if $k=1$, the ranks are $\O(\log n)$-bit numbers, but the data
1248 structure still requires $\Theta(n\log n)$ bits.
1250 We do a minor side step by remembering the complement of~$A$ instead, that is
1251 the set of the at most~$k$ elements we have already seen. We will call this set~$H$
1252 (because it describes the ``holes'' in~$A$). Since $\Omega(k\log n)$ bits are needed
1253 to represent the rank, the vector representation of~$H$ certainly fits in a~constant
1254 number of words. When we translate the operations on~$A$ to operations on~$H$,
1255 again stored as a~vector, we get:
1257 \thmn{Lexicographic ranking of $k$-permutations}
1258 When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both
1259 ranking and unranking can be performed on the RAM in time~$\O(k)$.
1261 \section{Restricted permutations}
1263 Another interesting class of combinatorial objects that can be counted and
1264 ranked are restricted permutations. An~archetypal member of this class are
1265 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
1266 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}
1267 We will present a~general (un)ranking method for any class of restricted
1268 permutations and derive a~linear-time algorithm for the derangements from it.
1271 We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
1272 all~permutations on~$[n]$.
1273 A~\df{restriction graph} is a~bipartite graph~$G$ whose parts are two copies
1274 of the set~$[n]$. A~permutation $\pi\in{\cal P}$ satisfies the restrictions
1275 if $(i,\pi(i))$ is an~edge of~$G$ for every~$i$.
1277 \paran{Equivalent formulations}%
1278 We will follow the path unthreaded by Kaplansky and Riordan
1279 \cite{kaplansky:rooks} and charted by Stanley in \cite{stanley:econe}.
1280 We will relate restricted permutations to placements of non-attacking
1281 rooks on a~hollow chessboard.
1284 A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
1285 A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares \hbox{$T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.}
1288 The traces of permutations (and thus the permutations themselves) correspond
1289 exactly to placements of $n$ rooks at the board in a~way such that the rooks do
1290 not attack each other (i.e., there is at most one rook in every row and
1291 likewise in every column; as there are $n$~rooks, there must be exactly one of them in
1292 every row and column). When speaking about \df{rook placements,} we will always
1293 mean non-attacking placements.
1295 Restricted permutations then correspond to placements of rooks on a~board with
1296 some of the squares removed. The \df{holes} (missing squares) correspond to the
1297 non-edges of~$G$, so $\pi\in{\cal P}$ satisfies the restrictions iff
1298 $T(\pi)$ avoids the holes.
1300 Placements of~$n$ rooks (and therefore also restricted permutations) can be
1301 also equated with perfect matchings in the restriction graph~$G$. The edges
1302 of the matching correspond to the squares occupied by the rooks, the condition
1303 that no two rooks share a~row nor column translates to the edges not touching
1304 each other, and the use of exactly~$n$ rooks is equivalent to the matching
1307 There is also a~well-known correspondence between the perfect matchings
1308 in a~bipartite graph and non-zero summands in the formula for the permanent
1309 of the bipartite adjacency matrix~$M$ of the graph. This holds because the
1310 non-zero summands are in one-to-one correspondence with the placements
1311 of~$n$ rooks on the corresponding board. The number of restricted
1312 permutations is therefore equal to the permanent of the matrix~$M$.
1314 The diversity of the characterizations of restricted permutations brings
1315 both good and bad news. The good news is that we can use the
1316 plethora of known results on bipartite matchings. Most importantly, we can efficiently
1317 determine whether there exists at least one permutation satisfying a~given set of restrictions:
1320 There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
1321 a~permutation satisfying a~given restriction graph. The $n$ and~$m$ are the number
1322 of vertices and edges of the restriction graph.
1324 The bad news is that computing the permanent is known to be~$\#\rm P$-complete even
1325 for zero-one matrices (as proven by Valiant \cite{valiant:permanent}).
1326 As a~ranking function for a~set of~matchings can be used to count all such
1327 matchings, we obtain the following theorem:
1330 If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
1331 a~set of restrictions which is a~part of the input, then $\rm P=\#P$.
1333 However, the hardness of computing the permanent is the only obstacle.
1334 We show that whenever we are given a~set of restrictions for which
1335 the counting problem is easy (and it is also easy for subgraphs obtained
1336 by deleting vertices), ranking is easy as well. The key will be once again
1337 a~recursive structure, similar to the one we have seen in the case of plain
1338 permutations in \ref{permrec}. We get:
1340 \thmn{Lexicographic ranking of restricted permutations}
1341 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}$
1342 and it is possible to calculate the permanent of~$M'$ in time $\O(t(n))$ for every matrix $M'$
1343 obtained by deletion of rows and columns from~$M_n$. Then there exist algorithms
1344 for ranking and unranking in ${\cal P}_{A,M_n}$ in time $\O(n^4 + n^2\cdot t(n))$
1345 if $M_n$ and an~$n$-element set~$A$ are given as a~part of the input.
1347 Our time bound for ranking of general restricted permutations section is obviously very coarse.
1348 Its main purpose was to demonstrate that many special cases of the ranking problem can be indeed computed in polynomial time.
1349 For most families of restriction matrices, we can do much better. These speedups are hard to state formally
1350 in general (they depend on the structure of the matrices), but we demonstrate them on the
1351 specific case of derangements. We show that each matrix can be sufficiently characterized
1352 by two numbers: the order of the matrix and the number of zeroes in it. We find a~recurrent
1353 formula for the permanent, based on these parameters, which we use to precalculate all
1354 permanents in advance. When we plug it in the general algorithm, we get:
1356 \thmn{Ranking of derangements}%
1357 For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
1358 lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
1360 \schapter{Conclusions}
1362 We have seen the many facets of the minimum spanning tree problem. It has
1363 turned out that while the major question of the existence of a~linear-time
1364 MST algorithm is still open, backing off a~little bit in an~almost arbitrary
1365 direction leads to a~linear solution. This includes classes of graphs with edge
1366 density at least $\lambda_k(n)$ for an~arbitrary fixed~$k$,
1367 minor-closed classes, and graphs whose edge weights are
1368 integers. Using randomness also helps, as does having the edges pre-sorted.
1370 If we do not know anything about the structure of the graph and we are only allowed
1371 to compare the edge weights, we can use the Pettie's MST algorithm.
1372 Its time complexity is guaranteed to be asymptotically optimal,
1373 but we do not know what it really is --- the best what we have is
1374 an~$\O(m\timesalpha(m,n))$ upper bound and the trivial $\Omega(m)$ lower bound.
1376 One thing we however know for sure. The algorithm runs on the weakest of our
1377 computational models ---the Pointer Machine--- and its complexity is linear
1378 in the minimum number of comparisons needed to decide the problem. We therefore
1379 need not worry about the details of computational models, which have contributed
1380 so much to the linear-time algorithms for our special cases. Instead, it is sufficient
1381 to study the complexity of MST decision trees. However, not much is known about these trees so far.
1383 As for the dynamic algorithms, we have an~algorithm which maintains the minimum
1384 spanning forest within poly-logarithmic time per operation.
1385 The optimum complexity is once again undecided --- the known lower bounds are very far
1386 from the upper ones.
1387 The known algorithms run on the Pointer machine and we do not know if using a~stronger
1390 For the ranking problems, the situation is completely different. We have shown
1391 linear-time algorithms for three important problems of this kind. The techniques,
1392 which we have used, seem to be applicable to other ranking problems. On the other
1393 hand, ranking of general restricted permutations has turned out to balance on the
1394 verge of $\#{\rm P}$-completeness. All our algorithms run
1395 on the RAM model, which seems to be the only sensible choice for problems of
1396 inherently arithmetic nature. While the unit-cost assumption on arithmetic operations
1397 is not universally accepted, our results imply that the complexity of our algorithm
1398 is dominated by the necessary arithmetics.
1400 Aside from the concrete problems we have solved, we have also built several algorithmic
1401 techniques of general interest: the unification procedures using pointer-based
1402 bucket sorting and the vector computations on the RAM. We hope that they will
1403 be useful in many other algorithms.
1405 \schapter{Bibliography}
1413 \rawchapter{Publications of Martin Mare\v{s}}
1418 \def\bibitem[#1]#2#3\par{\:\eatspaces #3}
1422 \def\newblock{\hskip .11em plus .33em minus .07em }%
1423 \def\citelist{\numlist\singlecit\rightskip=0pt}
1424 \def\singlecit{\global\advance\citecount by 1[\the\citecount]}
1429 \bibitem[Mar04]{mm:mst}
1431 \newblock {Two linear time algorithms for MST on minor closed graph classes}.
1432 \newblock {\em {Archivum Mathematicum}}, 40:315--320. Masaryk University, Brno,
1433 Czech Republic, 2004.
1435 \bibitem[MS07]{mm:rank}
1436 M.~Mare\v{s} and M.~Straka.
1437 \newblock Linear-time ranking of permutations.
1438 \newblock In {\em Algorithms --- ESA 2007: 15th Annual European Symposium},
1439 volume 4698 of {\em {Lecture Notes in Computer Science}}, pages 187--193.
1440 Springer Verlag, 2007.
1442 \bibitem[Mar07]{mm:ga}
1444 \newblock {Krajinou grafov\'ych algoritm\accent23u (Through the Landscape of
1446 \newblock ITI series 2007--330, Institut Teoretick\'e Informatiky, Praha, Czech
1450 \bibitem[Mar00]{mares:dga}
1452 \newblock {Dynamick\'e grafov\'e algoritmy (Dynamic Graph Algorithms)}.
1453 \newblock Master's thesis, Charles University in Prague, Faculty of Math and
1457 \bibitem[Mar07b]{mm:grading}
1459 \newblock {Perspectives on Grading Systems}.
1460 \newblock {\em Olympiads in Informatics}, 1:124--130. Institute of
1461 Mathematics and Informatics, Vilnius, Lithuania, 2007.
1465 \rawsection{Citations}
1469 %S. Tazari and M. Müller-Hannemann
1470 %Shortest Paths in Linear Time on Minor-Closed Graph Classes with an Application to Steiner Tree Approximation (abstract)
1471 %submitted for publication, 2007.
1473 \bibitem[HW07]{hochstein:maxflow}
1474 J.~M. Hochstein and K.~Weihe.
1475 \newblock {Maximum $s$-$t$-flow with $k$ crossings in $\O(k^3n \log n)$ time}.
1476 \newblock In {\em SODA 2007: Proceedings of the 18th annual ACM-SIAM symposium
1477 on Discrete algorithms}, pages 843--847, 2007.
1478 \newblock Cites~[1].
1480 \bibitem[MHT07]{tazari:mcgc}
1481 M.~M\"uller-Hannemann and S.~Tazari.
1482 \newblock {Handling Proper Minor-Closed Graph Classes in Linear Time: Shortest
1483 Paths and 2-Approximate Steiner Trees}.
1484 \newblock Tech Report 2007/5, University of Halle-Wittenberg, Institute of
1485 Computer Science, 2007.
1486 \newblock Cites~[1].
1493 \ifodd\pageno\else\hbox{}\fi