7 {\obeylines\parskip=0pt
8 \def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
9 \def\[#1]{~{\it(\ref{#1})}}
10 \n{$\bb R$}{the set of all real numbers}
11 \n{$\bb N$}{the set of all natural numbers, including 0}
12 \n{${\bb N}^+$}{the set of all positive integers}
13 \n{$\O(g)$}{asymptotic~$O$: $f=\O(g)$ iff $\exists c>0: f(n)\le g(n)$ for all~$n\ge n_0$}
14 \n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
15 \n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
16 \n{$\widetilde\O(g)$}{$f=\widetilde\O(g)$ iff $f=\O(g\cdot\log^{\O(1)} g)$}
17 \n{$\poly(n)$}{$f=\poly(n)$ iff $f=\O(n^c)$ for some $c$}
18 \n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
19 \n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
20 \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
21 \n{$G-e$}{graph $G$ with edge $e$ removed}
22 \n{$G+e$}{graph $G$ with edge $e$ added}
23 \n{$w(e)$}{weight of an edge $e$}
24 \n{$V(G)$}{set of vertices of a graph~$G$}
25 \n{$E(G)$}{set of edges of a graph~$G$}
26 \n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
27 \n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
28 \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
29 \n{$G[U]$}{subgraph induced by a~set $U\subset V(G)$}
30 \n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
31 \n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
32 \n{MST}{minimum spanning tree \[mstdef]}
33 \n{MSF}{minimum spanning forest \[mstdef]}
34 \n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
35 \n{$\msf(G)$}{the unique minimum spanning forest of a graph~$G$ \[mstnota]}
36 \n{$X \choose k$}{the set of all $k$-element subsets of a set~$X$}
37 \n{$G/e$}{multigraph contraction \[contract]}
38 \n{$G.e$}{simple graph contraction \[simpcont]}
39 \n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
40 \n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) \mid x\in X \}$}
41 \n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
42 \n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
43 \n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
44 \n{${\E}X$}{expected value of a~random variable~$X$}
45 \n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true}
46 \n{$\log n$}{a binary logarithm of the number~$n$}
47 \n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
48 \n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$}
49 \n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i \mid \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
50 \n{$\beta(m,n)$}{$\beta(m,n) := \min\{i \mid \log^{(i)}n \le m/n \}$ \[itjarthm]}
51 \n{$W$}{word size of the RAM \[wordsize]}
52 \n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]}
53 \n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
54 \n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]}
55 \n{$x[B]$}{when $x\in{\bb N}$: the values of the bits at positions in the set~$B$ \[qhnota]}
56 \n{$\pi[i]$}{when $\pi$ is a~sequence: the $i$-th element of~$\pi$, starting with $\pi[1]$ \[brackets]}
57 \n{$\pi[i\ldots j]$}{the subsequence $\pi[i], \pi[i+1], \ldots, \pi[j]$}
58 \n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
59 \n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
60 \n{$\equiv$}{congruence modulo a~given number}
61 \n{$\<LSB>(x)$}{the position of the lowest bit set in~$x$ \[lsbmsb]}
62 \n{$\<MSB>(x)$}{the position of the highest bit set in~$x$ \[lsbmsb]}
63 \n{$\bf x$}{a~vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
64 \n{$\band$}{bitwise conjunction: $(x\band y)[i]=1$ iff $x[i]=1 \land y[i]=1$}
65 \n{$\bor$}{bitwise disjunction: $(x\bor y)[i]=1$ iff $x[i]=1 \lor y[i]=1$}
66 \n{$\bnot$}{bitwise negation: $(\bnot x)[i]=1-x[i]$}
67 \n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
68 \n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
69 \n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
70 \n{$R_{C,\prec}(x)$}{the rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
71 \n{$R^{-1}_{C,\prec}(i)$}{the unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
72 \n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
73 \n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
74 \n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
75 \n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
76 \n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
77 \n{$K_k$}{the complete graph on~$k$ vertices}
78 \n{$C_k$}{the cycle on~$k$ vertices}
79 \n{${\cal P}_A$}{the set of all permutations on a~set~$A$ \[restnota]}
80 \n{${\cal P}_{A,M}$}{the set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]}
81 \n{$N_0(M)$}{the number of permutations satisfying the restrictions~$M$ \[restnota]}
82 \n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]}
83 \n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]}
84 \n{$\per M$}{the permanent of a~square matrix~$M$}
85 \n{$G\crpt R$}{graph~$G$ with edges in~$R$ corrupted \[corrnota]}
86 \n{$R^C$}{$R^C = R\cap \delta(C)$ \[corrnota]}
87 \n{${\cal D}(G)$}{The optimal MSF decision tree for a~graph~$G$ \[decdef]}
88 \n{$D(G)$}{The depth of ${\cal D}(G)$ \[decdef]}
89 \n{$D(m,n)$}{Decision tree complexity of MSF \[decdef]}
90 \n{$A(x,y)$}{The Ackermann's function \[ackerdef]}
91 \n{$A(x)$}{The diagonal Ackermann's function \[ackerdef]}
92 \n{$\lambda_i(n)$}{The inverse of the $i$-th row of the Ackermann's function \[ackerinv]}
93 \n{$\alpha(n)$}{The diagonal inverse of the Ackermann's function \[ackerinv]}
94 \n{$\alpha(m,n)$}{$\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}$ \[ackerinv]}
97 %--------------------------------------------------------------------------------
99 \section{Multigraphs and contractions}
101 Since the formalism of multigraphs is not fixed in the literature, we will
102 better define it carefully, following \cite{diestel:gt}:
104 \defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
105 set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
106 with the vertices, and $M$ is a mapping $E\rightarrow V \cup {V \choose 2}$
107 which assigns to each edge either a pair of vertices or a single vertex
108 (if the edge is a loop).
111 When the meaning is clear from the context, we use our notation originally
112 defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
113 shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
114 consider multigraphs with no multiple edges nor loops and simple graphs to be
115 the same objects, although they formally differ.
118 Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
119 produces a multigraph $G/e=(V',E',M')$ such that:
121 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
122 E' &= E(G) - \{e\},\cr
123 M'(f) &= \{ m(v) \mid v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
124 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
127 Sometimes we need contraction for simple graphs as well. It corresponds to performing
128 the multigraph contraction, unifying parallel edges and deleting loops.
131 Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
132 produces a graph $G.e=(V',E')$ such that:
134 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
135 E' &= \{ \{m(x),m(y)\} \mid xy\in E \land m(x)\ne m(y) \},\cr
136 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
140 We can also extend the above definitions to contractions by a~set of vertices or edges.
141 For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where
142 $f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result
143 does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$
144 as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$,
145 where $U^*$ is the complete graph on~$U$. Similarly for $G.F$ and $G.U$.
147 %--------------------------------------------------------------------------------
149 \section{Ackermann's function and its inverse}\id{ackersec}%
151 The Ackermann's function is an~extremely quickly growing function which has been
152 introduced by Ackermann \cite{ackermann:function} in the context of
153 computability theory. Its original purpose was to demonstrate that not every recursive
154 function is also primitive recursive. At the first sight, it does not
155 seem related to efficient algorithms at all. Its various inverses however occur in
156 analyses of various algorithms and mathematical structures surprisingly often:
157 We meet them in Section \ref{classalg} in the time complexity of the Disjoint Set Union
158 data structure and also in the best known upper bound on the decision tree
159 complexity of minimum spanning trees in Section \ref{optalgsect}. Another
160 important application is in the complexity of Davenport-Schinzel sequences (see
161 Klazar's survey \cite{klazar:gdss}), but as far as we know, these are not otherwise
162 related to the topic of our study.
164 Various sources differ in the exact definition of both the Ackermann's
165 function and its inverse, but most of the differences are in factors that
166 are negligible in the light of the giant asymptotic growth of the function.\foot{%
167 To quote Pettie \cite{pettie:onlineverify}: ``In the field of algorithms \& complexity,
168 Ackermann's function is rarely defined the same way twice. We would not presume to buck
169 such a~well-established precedent. Here is a~slight variant.''}
170 We will use the definition by double recursion given by Tarjan \cite{tarjan:setunion},
171 which is predominant in the literature on graph algorithms:
174 The \df{Ackermann's function} $A(x,y)$ is a~function on non-negative integers defined as follows:
178 A(x,1) &:= 2 \quad \hbox{for $x\ge 1$}, \cr
179 A(x,y) &:= A(x-1, A(x,y-1)) \quad \hbox{for $x\ge 1$, $y\ge 2$}. \cr
181 The functions $A(x,\cdot)$ are called the \df{rows} of $A(x,y)$, similarly $A(\cdot,y)$ are
184 Sometimes, a~single-parameter version of this function is also used. It is defined
185 as the diagonal of the previous function, i.e., $A(x):=A(x,x)$.
188 We can try evaluating $A(x,y)$ in some points:
190 A(x,2) &= A(x-1, A(x,1)) = A(x-1,2) = A(0,2) = 4, \cr
191 A(1,y) &= A(0, A(1,y-1)) = 2A(1,y-1) = 2^{y-1}A(1,1) = 2^y, \cr
192 A(2,y) &= A(1, A(2,y-1)) = 2^{A(2,y-1)} = 2\tower y \hbox{~~(the tower of exponentials),} \cr
193 A(3,y) &= \hbox{the tower function iterated $y$~times,} \cr
194 A(4,3) &= A(3,A(4,2)) = A(3,4) = A(2,A(3,3)) = A(2,A(2,A(3,2))) = \cr
195 &= A(2,A(2,4)) = 2\tower(2\tower 4) = 2\tower 65536. \cr
199 Three functions related to the inverse of the function~$A$ are usually considered:
202 The \df{$i$-th row inverse} $\lambda_i(n)$ of the Ackermann's function is defined by:
204 \lambda_i(n) := \min\{ y \mid A(i,y) > \log n \}.
206 The \df{diagonal inverse} $\alpha(n)$ is defined by:
208 \alpha(n) := \min\{ x \mid A(x) > \log n \}.
210 The two-parameter \df{alpha function} $\alpha(m,n)$ is defined for $m\ge n$ by:
212 \alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}.
216 $\lambda_1(n) = \O(\log\log n)$, $\lambda_2(n) = \O(\log^* n)$, $\lambda_3(n)$ grows even slower
217 and $\alpha(n)$ is asymptotically smaller than $\lambda_i(n)$ for any fixed~$i$.
220 It is easy to verify that all the rows are strictly increasing and so are all
221 columns, except the first three columns which are constant. Therefore for a~fixed~$n$,
222 $\alpha(m,n)$ is maximized at $m=n$. So $\alpha(m,n) \le 3$ when $\log n < A(3,4)$,
223 which covers all values of~$m$ that are likely to occur in practice.
226 $\alpha(m,n) \le \alpha(n)+1$.
229 $A(x,4\lceil m/n\rceil) \ge A(x,4) = A(x-1,A(x,3)) \ge A(x-1,x-1)$, so $A(x,4\lceil m/n\rceil)$
230 rises above $\log n$ no later than $A(x-1,x-1)$ does.
233 \lemma\id{alphaconst}%
234 When $i$~is a~fixed constant and $m\ge n\cdot \lambda_i(n)$, then $\alpha(m,n) \le i$.
237 The choice of~$m$ guarantees that $A(x,4\lceil m/n\rceil) \ge A(x,\lambda_i(n))$, which
238 is greater than $\log n$ for all $x \ge i$.