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