6 Warm-up: sampling a connected dominating set with the mean running-time exponent

This section combines the linear mean savings of Corollary 4.3 with the Steiner extension (Corollary 5.8) and the mean bound of Lemma 5.11. The resulting Algorithm RS is Algorithm MLS-\(\theta\) for connected dominating sets, run with a constant rate: it samples vertices of an unknown connected dominating set and completes the sample by a Steiner tree computation. We prove that it runs in randomized time \(O(1.7449^n)\) and polynomial space. At each solution fraction, the certified rate has a closed form (Proposition 6.1), and at solution fraction \(\frac12\) the corresponding base is exactly \(\sqrt3\). RS shows the mechanism in its simplest form: its analysis uses, through Jensen’s inequality, only the mean number of terminals of the samples inside a solution. Section 7 runs the same algorithm with a smaller rate and bounds the exponential moments directly on part of the range of solution sizes.

Throughout, \(\sigma=s/n\) denotes the solution fraction of a candidate size \(s\). The certified rate at \(\sigma\) is the infimum of the rates \(\psi\) (Section 3) for which our analysis gives condition (\(\star\)) for every connected dominating set of size \(s=\sigma n\). Algorithm RS uses one rate, \(\psi_{\mathrm{RS}}\), above the maximum of the certified rate over \(\sigma\). The certified rate is governed by the function \[\tag{14} F^*(\sigma)=H(\sigma)+(1-\sigma)\log\bigl(1-2^{-1/\sigma}\bigr)\qquad(0<\sigma<1),\] which is the function \(F^*\) of (6) with \(\beta=1\) and \(\rho=1/\sigma\): since \(2^x>x\) for every real \(x\), we have \(2^{1/\sigma}>1/\sigma\), that is \(p=2^{-1/\sigma}<\sigma\), so the second case of (6) applies, and \(\sigma\rho=1\) turns its last expression into (14). The corresponding base is \[2^{F^*(\sigma)}=\frac{\bigl(1-2^{-1/\sigma}\bigr)^{1-\sigma}}{\sigma^{\sigma}(1-\sigma)^{1-\sigma}} ,\] whose denominator is \(2^{-H(\sigma)}\), where \(2^{nH(\sigma)}\) is, up to a polynomial factor, the number of candidate sets of size \(\sigma n\), and whose numerator is the saving. We put \(F^*(1)=0\), the value of the right-hand side of (14) at \(\sigma=1\) and its limit as \(\sigma\to1\). By Remark 4.4, for \(\sigma<1\), \(F^*(\sigma)\) is the minimum over the sample fraction \(\tau\in[0,\sigma]\) of \[f_\sigma(\tau)=H(\tau)-\sigma H(\tau/\sigma)+1-\frac\tau\sigma ,\] whose first part is, up to an additive \(O(\log n)/n\) by (1), the loss \(\frac1n\log\left(\binom nt/\binom st\right)\) of requiring a uniform \(t\)-subset of \(V\) to lie inside a fixed connected dominating set of size \(s\), and whose second part, \(1-\tau/\sigma\), is the mean bound of Lemma 5.11 on the number of terminals, divided by \(n\). A single sample size and the Markov cutoff of Remark 4.2 attain this exponent up to the factors \(2^{1/\sigma}\) and \(s+1\) (Remark 4.4); Algorithm MLS-\(\theta\) attains it without rounding.

How RS decides.

For each candidate size \(s\), RS runs Algorithm MLS-\(\theta\) with a fixed rate. For each sample \(X\) it monitors the number of terminals \(|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\), which is computed in polynomial time, and compares it with the current threshold \(\theta\) (the thresholds of Algorithm MLS-\(\theta\), Section 3.2). A sample at or below the threshold is completed by the Steiner tree algorithm, in time at most \(2^{\theta}n^{O(1)}\); a sample above it is discarded in polynomial time.

The next proposition evaluates the certified rate at a given solution fraction: it gives the value at \(\sigma=\frac12\) and an upper bound on the maximum over \(\sigma\), together with two bounds on ranges of \(\sigma\) that Section 7 uses.

Proposition 6.1 (Certified rate of RS).  Let \(F^*\) be the function of (14).

(a)  For every \(\sigma\in(0,1)\), \(F^*(\sigma)<H(\sigma)\le1\), and the minimum of \(f_\sigma\) over \([0,\sigma]\) is attained exactly at \(\tau^*(\sigma)=\dfrac{\sigma-2^{-1/\sigma}}{1-2^{-1/\sigma}}\in(0,\sigma)\).

(b)  At \(\sigma=\frac12\): \(\tau^*=\frac13\) and \(F^*(\frac12)=\frac12\log3\), so the base \(2^{F^*(1/2)}\) is exactly \(\sqrt3\).

(c)  \(F^*(\sigma)\le\log1.744835\) for every \(\sigma\in(0,1]\). Moreover \(F^*(\sigma)\le0.7807\) for \(\sigma\in(0,0.31]\) and \(F^*(\sigma)\le0.7802\) for \(\sigma\in[0.54,1]\).

Lean proof: rs_rate_a, rsfσ_min_eq, rs_rate_b, rs_rate_b_argmin, rs_base_denom, rs_base, rsfσ_eq_fσ, rsTau_eq_τstar, rs_rate_c, rsF_one, rsF_eq_Fstar (formalisation) · Certificates: rs_closed_form_interval.py

Proof. (a) The first claim holds because \(\log(1-2^{-1/\sigma})<0\) and \(H\le1\). The second is Remark 4.4 with \(p=2^{-1/\sigma}<\sigma\).

(b) Here \(2^{-1/\sigma}=\frac14\) and \(\tau^*=\frac{1/2-1/4}{3/4}=\frac13\), and \(2^{F^*(1/2)}=(\frac34)^{1/2}/\frac12=\sqrt3\).

(c) The certificate of Appendix F.1 gives \(F^*(\sigma)\le0.8030906143<\log1.744835\) for every \(\sigma\in[0.2,0.8]\), \(F^*\le0.7807\) on \([0.15,0.31]\) and \(F^*\le0.7802\) on \([0.54,0.8]\). For \(\sigma\in(0,1)\setminus[0.2,0.8]\), (a) gives \(F^*(\sigma)\le H(\sigma)\le H(0.2)=\log5-1.6<0.73\), because \(H\) is increasing on \([0,\frac12]\) and symmetric about \(\frac12\), and \(5^{100}<2^{233}\); and \(F^*(1)=0\). As \(0.73<0.7802\), this bound covers the rest of the two ranges.  ∎

The closed form bounds the exponential moments of Definition 3.3 for every connected dominating set; the corollary is used again in Section 7.

Corollary 6.2 (Closed-form moment bound).  Let \(G\) be a connected graph with \(n\) vertices and let \(S\) be a connected dominating set of \(G\) with \(|S|=s\) and \(\sigma=s/n\). Then, for the running-time exponent \(g(X)=|\mathrm{T}(J_X)|\) of Corollary 5.8, \[\max_{0\le t\le s}\frac{\mu_t(S)}{\binom nt}\ \ge\ \frac{2^{-nF^*(\sigma)}}2 .\]

Lean proof: rs_moments (formalisation)

Proof. If \(s=n\), then \(S=V\), \(\mu_n(S)=2^{-|\mathrm{T}(J_V)|}=\frac12\) by (13), and \(F^*(1)=0\). Otherwise \(n\ge2\) and \(\sigma\in(0,1)\). For \(1\le t\le s\), Lemma 5.11 gives \[\mathbb{E}_{X\in\binom St}|\mathrm{T}(J_X)|\le n-1-\frac{t(n-2)}s=n-\frac t\sigma+\frac{2t}s-1\le n-\frac t\sigma+1,\] as \(t\le s\), and for \(t=0\) we have \(|\mathrm{T}(J_\emptyset)|=n\le n+1\). So (7) holds with \(\beta=1\), \(\rho=1/\sigma\) and \(C=1\) for every connected dominating set of size \(s\), and Corollary 4.3(1) gives \(G(S)\le2^{1+nF^*(\sigma)}\) with \(F^*\) as in (14). The first inequality of Lemma 3.9 gives \(\min_{0\le t\le s}\binom nt/\mu_t(S)=M(S)\le G(S)\).  ∎

We can now state the algorithm.

Algorithm 6.3 (RS).  a connected graph \(G\) with \(n\) vertices. \(\psi_{\mathrm{RS}}=0.80309062\) and a constant \(\kappa>0\). For \(s=1,2,\dots,n\) in turn, run Algorithm MLS-\(\theta\)\((\psi_{\mathrm{RS}},2,\kappa)\) (Algorithm 3.4) on \((G,s)\) for the implicit set system \(\Phi_{\mathrm{CDS}}\), the extension algorithm \(\mathcal{A}_{\mathrm{St}}\) and the running-time exponent \(g\) of Corollary 5.8, written \(g(X)=g(G,X,s)=|\mathrm{T}(J_X)|\) as declared after that corollary. Output the first \(s\) for which the run answers yes, and output \(n\) if there is none.

Theorem 6.4 (Algorithm RS).  For every constant \(\kappa>0\), Algorithm RS runs in time \(O(1.7449^n)\) and polynomial space. It never outputs a value below \(\gamma_{\mathrm{c}}(G)\), and it outputs \(\gamma_{\mathrm{c}}(G)\) with probability at least \(1-e^{-\kappa}\). Consequently Connected Dominating Set and Max Leaf Spanning Tree (by Lemma 5.1, and directly when \(n\le2\)) can be solved by a randomized algorithm with one-sided error (one-sided Monte Carlo) in time \(O(1.7449^n)\) and polynomial space.

Lean, partial: rs_star, rs_constants (formalisation)

Proof. We verify the hypotheses of Lemma 5.2 for the run on \((G,s)\). By Corollary 5.8, \(\mathcal{A}_{\mathrm{St}}\) solves \(\Phi_{\mathrm{CDS}}\)-Extension in polynomial space with the running-time exponent \(g\), and the parameters \(\psi_{\mathrm{RS}}\), \(\Gamma=2\) and \(\kappa\) are constants. So Theorem 3.5 applies: the run takes time \(2^{\psi_{\mathrm{RS}}n}n^{O(1)}\) and polynomial space, and it answers no if \(\gamma_{\mathrm{c}}(G)>s\).

Completeness. Let \(s=\gamma_{\mathrm{c}}(G)\) and let \(S\) be a connected dominating set with \(|S|=s\). By Corollary 6.2 and Proposition 6.1(c), \[\max_{0\le t\le s}\frac{\mu_t(S)}{\binom nt}\ \ge\ \frac{2^{-n\log1.744835}}2\ \ge\ \frac{2^{-\psi_{\mathrm{RS}}n}}2,\] as \(\psi_{\mathrm{RS}}>\log1.744835\); that is, \(S\) satisfies (\(\star\)) with \(\Gamma=2\). By Theorem 3.5(iii), the run on \((G,\gamma_{\mathrm{c}}(G))\) answers yes with probability at least \(1-e^{-\kappa}\).

Lemma 5.2 now gives the statements about the output, and the total time is \(n\cdot2^{\psi_{\mathrm{RS}}n}n^{O(1)}=O(1.7449^n)\), because \(2^{\psi_{\mathrm{RS}}}=1.744835\ldots<1.7449\), where the constant \(1.744835\) comes from Proposition 6.1(c).  ∎