{\obeylines\parskip=0pt
\def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
-\def\[#1]{[\ref{#1}]}
+\def\[#1]{~{\it(\ref{#1})}}
\n{$\bb R$}{the set of all real numbers}
\n{$\bb N$}{the set of all natural numbers, including 0}
\n{${\bb N}^+$}{the set of all positive integers}
+\n{$\O(g)$}{asymptotic~$O$: $f=\O(g)$ iff $\exists c>0: f(n)\le g(n)$ for all~$n\ge n_0$}
+\n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
+\n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
+\n{$\widetilde\O(g)$}{$f=\widetilde\O(g)$ iff $f=\O(g\cdot\log^{\O(1)} g)$}
+\n{$\poly(n)$}{$f=\poly(n)$ iff $f=\O(n^c)$ for some $c$}
\n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
\n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
\n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
\n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
\n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
\n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
+\n{$G[U]$}{subgraph induced by a~set $U\subset V(G)$}
\n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
\n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
\n{MST}{minimum spanning tree \[mstdef]}
\n{$X \choose k$}{a set of all $k$-element subsets of a set~$X$}
\n{$G/e$}{multigraph contraction \[contract]}
\n{$G.e$}{simple graph contraction \[simpcont]}
+\n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
\n{$\alpha(n)$}{the inverse Ackermann's function}
\n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$}
\n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
\n{$\log n$}{a binary logarithm of the number~$n$}
\n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
\n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$}
-\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n < 1\}$; the inverse of~$2\tower n$}
-\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n < m/n \}$ \[itjarthm]}
+\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
+\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n \le m/n \}$ \[itjarthm]}
\n{$W$}{word size of the RAM \[wordsize]}
+\n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]}
+\n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
+\n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]}
+\n{$x[B]$}{when $x\in{\bb N}$: the values of the bits at positions in the set~$B$ \[qhnota]}
+\n{$\pi[i]$}{when $\pi$ is a~sequence: the $i$-th element of~$\pi$, starting with $\pi[1]$ \[brackets]}
+\n{$\pi[i\ldots j]$}{the subsequence $\pi[i], \pi[i+1], \ldots, \pi[j]$}
+\n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
+\n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
+\n{$\equiv$}{congruence modulo a~given number}
+\n{$\<LSB>(x)$}{the position of the lowest bit set in~$x$ \[lsbmsb]}
+\n{$\<MSB>(x)$}{the position of the highest bit set in~$x$ \[lsbmsb]}
+\n{$\bf x$}{a~vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
+\n{$\band$}{bitwise conjunction: $(x\band y)[i]=1$ iff $x[i]=1 \land y[i]=1$}
+\n{$\bor$}{bitwise disjunction: $(x\bor y)[i]=1$ iff $x[i]=1 \lor y[i]=1$}
+\n{$\bnot$}{bitwise negation: $(\bnot x)[i]=1-x[i]$}
+\n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
+\n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
+\n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
+\n{$R_{C,\prec}(x)$}{the rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
+\n{$R^{-1}_{C,\prec}(i)$}{the unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
+\n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
+\n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
+\n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
+\n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
+\n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
+\n{$K_k$}{the complete graph on~$k$ vertices}
+\n{$C_k$}{the cycle on~$k$ vertices}
+\n{${\cal P}_A$}{the set of all permutations on a~set~$A$ \[restnota]}
+\n{${\cal P}_{A,M}$}{the set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]}
+\n{$N_0(M)$}{the number of permutations satisfying the restrictions~$M$ \[restnota]}
+\n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]}
+\n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]}
+\n{$\per M$}{the permanent of a~square matrix~$M$}
}
%--------------------------------------------------------------------------------
\defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
-with the vertices, and $M$ is a mapping $E\mapsto V \cup {V \choose 2}$
+with the vertices, and $M$ is a mapping $E\rightarrow V \cup {V \choose 2}$
which assigns to each edge either a pair of vertices or a single vertex
(if the edge is a loop).
m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
}$$
-%--------------------------------------------------------------------------------
-
-\section{Models of computation}
-
-Traditionally, computer scientists use a~variety of computational models
-for a~formalism in which their algorithms are stated. If we were studying
-NP-completeness, we could safely assume that all the models are equivalent,
-possibly up to polynomial slowdown, which is negligible. In our case, the
-differences between good and not-so-good algorithms are on a~much smaller
-scale, so we need to replace yardsticks with a~micrometer and define our
-computation model carefully.
-
-We would like to keep the formalism close enough to the reality of the contemporary
-computers. This rules out Turing machines and similar sequentially addressed
-models, but even the remaining models are subtly different. For example, some of them
-allow indexing of arrays in constant time, while the others have no such operation
-and arrays have to be emulated with pointer structures, requiring $\Omega(\log n)$
-time to access a~single element of an~$n$-element array. It is hard to say which
-way is superior --- most ``real'' computers have instructions for constant-time
-indexing, but on the other hand it seems to be physically impossible to fulfil
-this promise with an~arbitrary size of memory. Indeed, at the level of logical
-gates, the depth of the actual indexing circuits is logarithmic.
-
-In recent decades, most researchers in the area of combinatorial algorithms
-were considering two computational models: the Random Access Machine and the Pointer
-Machine. The former one is closer to the programmer's view of a~real computer,
-the latter one is slightly more restricted and ``asymptotically safe.''
-We will follow this practice and study our algorithms in both models.
-
-\para
-The \df{Random Access Machine (RAM)} is not a~single model, but rather a~family
-of closely related models, sharing the following properties.
-(See Cook and Reckhow \cite{cook:ram} for one of the common formal definitions
-and Hagerup \cite{hagerup:wordram} for a~thorough description of the differences
-between the RAM variants.)
-
-The \df{memory} of the model is represented by an~array of \df{memory cells}
-addressed by non-negative integers, each of them containing a~single non-negative integer.
-The \df{program} is a~sequence of \df{instructions} of two basic kinds: calculation
-instructions and control instructions.
-
-\df{Calculation instructions} have two source arguments and one destination
-argument, each \df{argument} being either an~immediate constant (not available
-as destination), a~directly addressed memory cell (specified by its number)
-or an~indirectly addressed memory cell (its address is stored in a~directly
-addressed memory cell).
-
-\df{Control instructions} include branches (to a~specific instruction in
-the program), conditional branches (e.g., jump if two arguments specified as
-in the calculation instructions are equal) and an~instruction to halt the program.
-
-At the beginning of the computation, the memory contains the input data
-in specified memory cells and arbitrary values in all other cells.
-Then the program is executed one instruction at a~time. When it halts,
-specified memory cells are interpreted as the program's output.
-
-\para\id{wordsize}%
-In the description of the RAM family, we have omitted several properties
-on~purpose, because different members of the family define them differently.
-These are: the size of the available integers, the time complexity of a~single
-instruction, the space complexity of a~single memory cell and the repertoire
-of operations available in calculation instructions.
-
-If we impose no limits on the magnitude of the numbers and we assume that
-arithmetic and logical operations work on them in constant time, we get
-a~very powerful parallel computer --- we can emulate an~exponential number
-of parallel processors using arithmetics and suddenly almost everything can be
-computed in constant time, modulo encoding and decoding of input and output.
-Such models are unrealistic and there are two basic possibilities how to
-avoid this behavior:
-
-\numlist\ndotted
-\:Keep unbounded numbers, but increase costs of instructions: each instruction
- consumes time proportional to the number of bits of the numbers it processes,
- including memory addresses. Similarly, space usage is measured in bits,
- counting not only the values, but also the addresses of the respective memory
- cells.
-\:Place a~limit on the size of the numbers ---define the \df{word size~$W$,}
- the number of bits available in the memory cells--- and keep the cost of
- of instructions and memory cells constant. The word size must not be constant,
- since we can address only~$2^W$ cells of memory. If the input of the algorithm
- is stored in~$N$ cells, we need~$W\ge\log N$ just to be able to read the input.
- On the other hand, we are interested in polynomial-time algorithms only, so $\Theta(\log N)$-bit
- numbers should be sufficient. In practice, we pick~$w$ to be the larger of
- $\Theta(\log N)$ and the size of integers used in the algorithm's input and output.
-\endlist
-
-Both restrictions easily avoid the problems of unbounded parallelism. The first
-choice is theoretically cleaner and Cook et al.~show nice correspondences to the
-standard complexity classes, but the calculations of time and space complexity tend
-to be somewhat tedious. What more, when compared with the RAM with restricted
-word size, the complexities are usually exactly $\Theta(w)$ times higher.
-This does not hold in general (consider a~program which uses many small numbers
-and $\O(1)$ large ones), but it is true for the algorithms we are interested in.
-Therefore we will always assume that the operations have unit cost and we make
-sure that all numbers are limited by the available word size.
-
-\para
-As for the choice of RAM operations, the following three instruction sets are used:
-
-\itemize\ibull
-\:\df{Word-RAM} --- allows the ``C-language operators'', i.e., addition,
- subtraction, multiplication, division, remainder, bitwise {\sc and,} {\sc or,} exclusive
- {\sc or} ({\sc xor}), negation ({\sc not}) and bitwise shifts ($\ll$ and~$\gg$).
-\:\df{${\rm AC}^0$-RAM} --- allows all operations from the class ${\rm AC}^0$, i.e.,
- those computable by constant-depth polynomial-size boolean circuits with unlimited
- fan-in and fan-out. This includes all operations of the Word-RAM except for multiplication,
- division and remainders, and also many other operations like computing the Hamming
- weight (number of bits set in a~given number).
-\:Both restrictions at once.
-\endlist
-
-Thorup discusses the usual techniques employed by RAM algorithms in~\cite{thorup:aczero}
-and he shows that they work on both Word-RAM and ${\rm AC}^0$-RAM, but the combination
-of the two restrictions is too weak. On the other hand, taking the intersection of~${\rm AC}^0$
-with the instruction set of modern processors (like the multimedia instructions of Intel's Pentium4)
-is already strong enough.
-
-\FIXME{References to CPU manuals}
-
-We will therefore use the Word-RAM instruction set, mentioning differences with
-${\rm AC}^0$-RAM where necessary.
-
-\nota
-When speaking of the \df{RAM,} we implicitly mean the version with numbers limited
-by a~specified word size of $W$~bits, unit cost of operations and memory cells and the instruction
-set of the Word-RAM. This corresponds to the usage in recent algorithmic literature,
-although the authors rarely mention the details.
-
+\defn\id{setcont}%
+We can also extend the above definitions to contractions by a~set of vertices or edges.
+For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where
+$f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result
+does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$
+as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$,
+where $U^*$ is the complete graph on~$U$. Similarly for $G.F$ and $G.U$.
\endpart
projects / saga.git / blobdiff