10 Deterministic algorithms in polynomial space
The algorithms of Sections 6, 7 and 8 are randomized. With the balanced set-inclusion families of Section 9, we derandomize the exponential moments of an integer affine surrogate of the number of terminals (Theorem 10.4). The resulting algorithm runs in polynomial space, below the \(O^{*}(1.8619^n)\) of Abu-Khzam, Mouawad and Liedloff (Abu-Khzam, Mouawad, and Liedloff 2011). It escapes the black-box barrier of Corollary 9.3 because it uses an affine upper bound on the running-time exponent, the pointwise tree inequality of Lemma 5.10, and not only the values of the exponent. It does not reach the randomized bounds of Sections 7 and 8: their analyses bound the running-time exponent through tests along an unknown spanning tree of the solution, which are not separable over the fixed block partitions of the balanced families.
Setting.
All graphs are connected, with \(n\) vertices. We use the implicit set system \(\Phi_{\mathrm{CDS}}\) of connected dominating sets, the Steiner extension algorithm \(\mathcal{A}_{\mathrm{St}}\) and its running-time exponent (Definition 3.2, with the graph \(G\) as the instance \(I\)) \[g(G,X,k)=|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\] from Corollary 5.8: \(\mathcal{A}_{\mathrm{St}}\) decides whether \(X\) extends to a connected dominating set with at most \(k\) vertices, deterministically, in time \(2^{|\mathrm{T}(J_X)|}n^{O(1)}\) and polynomial space. The running-time exponent does not depend on \(k\). The certificate is the pointwise form of the tree inequality: if \(S\) is a connected dominating set and \(F\) a spanning tree of \(G\) in which every vertex outside \(S\) is a leaf, the integer weights \(w(v)=d_F(v)-1\ge0\) on \(S\) satisfy \[\tag{19} w(S)=n-2\qquad\text{and}\qquad|\mathrm{T}(J_X)|\le n-1-w(X)\ \text{ for every nonempty }X\subseteq S,\] by Lemma 5.10 and (13) (for \(n\ge2\)). In the language of Section 9, (19) is an integer certificate (Theorem 9.10) with \(\alpha=n-1\) and total weight \(\Xi=n-2\).
The algorithm decides, for \(s=1,\dots,n\), whether \(G\) has a connected dominating set of size \(s\), by enumeration for small and large \(s\) and by Algorithm 9.9 in between (Lemma 10.3), and outputs the least \(s\) at which it answers yes. By Lemma 5.1, every bound below holds for Max Leaf Spanning Tree as well.
10.1 Two weight classes
For the integer weights of (19), we express the running-time bound of Theorem 9.10 through the following function. For \(u\in(0,1]\) put \(a=\lfloor1/u\rfloor\) and, for \(y>0\), \[\chi_y(u)=\log(1+y)+1-\bigl((a+1)u-1\bigr)\log\bigl(1+y2^{a}\bigr)-(1-au)\log\bigl(1+y2^{a+1}\bigr).\] Here \(u\) will be \(s/\Xi\), the ratio of the solution size to the total weight \(\Xi\) (\(\Xi=n-2\) here, \(\Xi=n-1\) in Section 12.3), and the two coefficients are the fractions (relative to \(\Xi\)) of solution vertices of weight \(a\) and \(a+1\) in the balanced integer profile of Lemma 9.7. The next lemma bounds \(\inf_{y>0}\chi_y(u)\) on the range of \(u\) that the algorithm meets, with one explicit \(y\) for each range of \(u\).
Lemma 10.1 (Rate certificate). For every \(u\in[0.15,0.85]\) there is \(y\in\{\frac{1+\sqrt5}8,\frac12,\frac5{16},\frac14,\frac{27}{128},\frac{29}{160}\}\) with \(\chi_y(u)\le\log(\sqrt5-\frac12)\).
Lean proof: det_cert (formalisation) · Certificates: rates.py, v_rates.py
Further optimization over \(y\) does not appear to lower this bound (Appendix F); the proof does not use this.
With the rate certificate in hand, the integer-affine algorithm gives the deterministic bound.
The running time of the integer-affine algorithm with a certificate of this shape depends only on \(n\), \(s\), \(\alpha\) and \(\Xi\). We record it once, for the two parameter pairs that occur in this paper (\(\Xi=n-2\) here, \(\Xi=n-1\) for weak connectivity in Section 12.3).
Lemma 10.2 (Running time of the integer-affine algorithm for tree-type certificates). Let \(n\ge34\), \(0.15n<s<0.8n\), \(\Xi\in\{n-2,n-1\}\) and \(\alpha=\Xi+1\). For every implicit set system, extension algorithm and running-time exponent with values in \(\{0,\dots,n\}\), Algorithm 9.9 on \((I,k=s,\alpha,\Xi)\) runs in time \[\bigl(\sqrt5-\tfrac12\bigr)^{n}\,2^{O(n(\log\log n)^{2}/\log n)}\,N^{O(1)} .\]
The next lemma packages one run of the integer-affine algorithm, together with enumeration for the solution sizes that Lemma 10.2 excludes, as a deterministic decision procedure for one solution size; Section 12 uses it for the variants.
Lemma 10.3 (Deterministic decision for one size). Let \(\Phi\) be an implicit set system, let \(\mathcal{A}\) be a deterministic algorithm that solves \(\Phi\)-Extension with a running-time exponent \(g\) with values in \(\{0,\dots,n\}\), and let \((\alpha,\Xi)\in\{(n-1,n-2),(n,n-1)\}\). For an instance \(I\) with a universe of \(n\) elements and \(1\le s\le n\), let \(\mathrm{Det}(I,s)\) be the following procedure: if \(n<34\), or \(s\le0.15n\), or \(s\ge0.8n\), test every \(s\)-subset of \(U_I\) for membership in \(\mathcal{F}_I\) and answer yes if and only if one of them is a solution; otherwise run Algorithm 9.9 on \((I,k=s,\alpha,\Xi)\) with \(\mathcal{A}\) and \(g\). Then \(\mathrm{Det}\) is deterministic, runs in time \((\sqrt5-\frac12)^{n}2^{O(n(\log\log n)^{2}/\log n)}N^{O(1)}\) and in space \(N^{O(1)}\) plus the space of \(\mathcal{A}\), answers no if \(\mathcal{F}_I\) has no solution of size at most \(s\), and answers yes whenever \(\mathcal{F}_I\) has a solution \(S\) of size exactly \(s\) which, in the case \(n\ge34\) and \(0.15n<s<0.8n\), has an integer certificate for \((\alpha,\Xi)\) in the sense of Theorem 9.10.
The proofs of Lemmas 10.1, 10.2 and 10.3 and of the following theorem are in Appendix D.8.2. The theorem runs \(\mathrm{Det}(G,s)\) of Lemma 10.3 for \(s=1,\dots,n\) with \((\alpha,\Xi)=(n-1,n-2)\), for which the weights of (19) are an integer certificate of every minimum connected dominating set.
Theorem 10.4 (Deterministic Connected Dominating Set and MaxLeaf). Connected Dominating Set, and hence Max Leaf Spanning Tree (by Lemma 5.1, and directly when \(n\le2\)), can be solved by a deterministic algorithm in time \[O\Bigl(\bigl(\sqrt5-\tfrac12\bigr)^{n}\,2^{O(n(\log\log n)^{2}/\log n)}\Bigr)=O(1.7361^{n})\] and polynomial space, where \(\sqrt5-\frac12=1.7360\ldots\).
What Theorem 10.4 derandomizes.
By Proposition 9.8, the randomized exponential-moment theorem (Theorem 3.5) applied to the surrogate exponent \(\alpha-w(X)\) certifies, in the worst case over integer certificates of total \(\Xi\), the running-time bound \(\inf_y(1+y)^{n}2^{\alpha}/\mathsf P^*(y)\) up to polynomial factors; whenever the infimum may be taken over \(y\) with \(\mathsf P^*(y)\ge2\), this agrees with the bound of Theorem 9.10 up to a factor \(2\). So Theorems 9.10 and 10.4 derandomize the exponential-moment bound of the integer affine surrogate, here \(n-1-w(X)\), of the number of terminals, up to a factor \(2^{o(n)}\) in the running time; they do not derandomize Theorem 3.5 for the true running-time exponent, whose exponential moments can be much larger. The surrogate bound \(1.7361^n\) already improves on the mean-exponent analysis of Algorithm RS (\(1.7449^n\)), but not on Algorithm RS-\(\theta\) (\(1.7204^n\), Theorem 7.2), whose tree potential captures correlations that the surrogate discards, nor on RSC (\(1.6991^n\), Theorem 8.1). The factor \(2^{o(n)}\) that the balanced families contribute is large for practical \(n\), about \(2^{12718}\) at \(n=1000\) (Appendix D.7).