7 Exponential moments of the Steiner extension: Algorithm RS-\(\theta\)
The analysis of Algorithm RS in Section 6 uses, through Jensen’s inequality, only the mean number of terminals of the samples inside a solution. By Proposition 5.12 the bound of Lemma 5.11 on this mean cannot be improved, but how it is used can: when the number of terminals fluctuates, Jensen’s inequality \(\mathbb{E}[2^{-|\mathrm{T}(J_X)|}]\ge2^{-\mathbb{E}|\mathrm{T}(J_X)|}\) is strict, and the samples with few terminals account for the difference. Algorithm RS-\(\theta\) is Algorithm RS run with a smaller rate: it is Algorithm MLS-\(\theta\) (Algorithm 3.4) for connected dominating sets with the Steiner extension of Corollary 5.8, and its success condition in Theorem 3.5 is condition (\(\star\)) on the exponential moments \(\mu_t(S)\) of the number of terminals, which we now bound directly. We prove that it runs in randomized time \(O(1.7204^n)\) and polynomial space (Theorem 7.2).
The analysis needs a lower bound on these moments for every connected dominating set. Since \(\mathbb{E}[2^{-|\mathrm{T}(J_X)|}]\) is not linear in \(|\mathrm{T}(J_X)|\), the linearity-of-expectation argument behind Lemma 5.11 does not apply. We bound the number of terminals by a potential that is local along a spanning tree of the solution (Lemma 7.3), evaluate its generating function by a three-state recursion (Lemma 7.4), and bound the recursion from below, uniformly over all trees, by an antinorm certificate (Lemma 7.5), following Rote (Rote 2019) and Rosenfeld (Rosenfeld 2021). The proofs of these three steps are in Appendix D.4. Condition (\(\star\)) is then verified at every solution fraction by two certificates or by the closed form of Section 6 (Table 3). On the uniform \((2,2)\)-lobsters the analysis is nearly tight for this algorithm (Proposition 7.9).
For a connected graph \(G\) and the running-time exponent \(g\) of Corollary 5.8, written \(g(X)=g(G,X,s)=|\mathrm{T}(J_X)|\) in the shorthand of Definition 3.2 with target size \(k=s\), the quantities of Definition 3.3 for a connected dominating set \(S\) with \(|S|=s\) are \[\tag{15} \mu_t(S)=\sum_{X\in\binom St}2^{-|\mathrm{T}(J_X)|}\quad(0\le t\le s),\qquad W_S(y)=\sum_{X\subseteq S}y^{|X|}\,2^{-|\mathrm{T}(J_X)|}\quad(y\ge0);\] the running-time exponent does not depend on the size bound \(k\). Recall from (13) that \(|\mathrm{T}(J_X)|\) is an integer in \(\{0,\dots,n\}\), that \(|\mathrm{T}(J_\emptyset)|=n\) and that \(|\mathrm{T}(J_S)|=1\).
7.1 The algorithm and the result
Algorithm 7.1 (RS-\(\theta\)). a connected graph \(G\) with \(n\) vertices. \(\psi^*=0.7827016\) and a constant \(\kappa>0\). For \(s=1,2,\dots,n\) in turn, run Algorithm MLS-\(\theta\)\((\psi^*,2,\kappa)\) on \((G,s)\) for the implicit set system \(\Phi_{\mathrm{CDS}}\), the extension algorithm \(\mathcal{A}_{\mathrm{St}}\) and the running-time exponent \(g(X)=|\mathrm{T}(J_X)|\) of Corollary 5.8, as in Algorithm RS. Output the first accepted \(s\), or \(n\) if no \(s\) is accepted.
So RS-\(\theta\) differs from RS only in its rate, and the improvement lies in the analysis. The analysis of RS bounds the moments \(\mu_t(S)\) through the mean of Lemma 5.11, whereas the analysis below chooses, for each minimum connected dominating set \(S\), a pair \((t,\theta)\) at which the number of samples \(X\subseteq S\) of size \(t\) with \(|\mathrm{T}(J_X)|\le\theta\) is, up to a polynomial factor, at least \(2^\theta\mu_t(S)\) (Lemma 3.8). For instance, the pair \(t=s\), \(\theta=1\) replaces enumeration of the \(s\)-sets: each of its trials draws a uniform \(s\)-set \(X\), and the threshold test passes exactly when \(X\) is a connected dominating set. The main result of this section is the following.
Theorem 7.2 (Algorithm RS-\(\theta\)). For every constant \(\kappa>0\), Algorithm RS-\(\theta\) runs in time \(O^{*}(2^{\psi^*n})\), where \(2^{\psi^*}=1.7203\ldots<1.7204\), and in 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.7204^n)\) and polynomial space.
Lean, partial: rst_rates (formalisation)
The proof is given at the end of Section 7.5; it rests on Proposition 7.8, which verifies condition (\(\star\)) for every connected dominating set. The constant \(1.7204\) rests on Proposition 7.7 and Proposition 6.1(c).
7.2 Reduction to a tree with an owner map
The first step replaces the graph by a tree. Let \(S\) be a connected dominating set of \(G\). An owner map is a map \(o:V\setminus S\to S\) with \(o(u)\in N(u)\) for every \(u\notin S\); it exists because \(S\) is dominating. For \(v\in S\) let \(\nu_v=|o^{-1}(v)|\) be the number of vertices that \(v\) owns, so that \(\sum_{v\in S}\nu_v=n-|S|\). For a tree \(F\) with \(V(F)=S\), a map \(\nu:S\to\mathbb Z_{\ge0}\) and \(X\subseteq S\) put \[\tag{16} \begin{gathered} \Pi_{F,\nu}(X)=\sum_{v\in S\setminus X}\nu_v\;+\;\bigl|\{v\in S:N_F[v]\cap X=\emptyset\}\bigr| \;+\;\operatorname{comp}(F[X]),\\ W_{F,\nu}(y)=\sum_{X\subseteq S}y^{|X|}\,2^{-\Pi_{F,\nu}(X)} . \end{gathered}\] The three terms count, in order: the owned vertices whose owner is not sampled, the solution vertices not dominated by a sample within the tree, and the components of the sample within the tree. We call \(\Pi_{F,\nu}\) the potential; the next lemma shows that it is at least the running-time exponent \(|\mathrm{T}(J_X)|\) of every sample \(X\subseteq S\).
Lemma 7.3 (Tree reduction). Let \(G\) be a connected graph, let \(S\) be a connected dominating set of \(G\), let \(F\) be a spanning tree of \(G[S]\) and let \(o\) be an owner map with counts \(\nu\). Then for every \(X\subseteq S\), \[|\mathrm{T}(J_X)|\ \le\ \Pi_{F,\nu}(X).\] Equality holds for every \(X\subseteq S\) if \(G[S]=F\) and every vertex of \(V\setminus S\) has exactly one neighbor in \(S\). Consequently \(W_S(y)\ge W_{F,\nu}(y)\) for every \(y\ge0\).
Lean proof: tree_reduction, moment_bound_of_tree_bound, rstheta_moment_bound_0, rstheta_moment_bound_1, tree_reduction_eq (formalisation)
7.3 A three-state recursion
The second step computes \(W_{F,\nu}(y)\) by dynamic programming over the tree. Root \(F\) at a vertex \(r\); for \(v\in V(F)\) let \(F_v\) be the subtree formed by \(v\) and its descendants. A message is a vector \(P=(P_1,P_2,P_3)\in\mathbb{R}^3\) whose coordinates are sums of weights \(y^{|X|}2^{-\Pi^{\mathrm{in}}(X)}\), where \(\Pi^{\mathrm{in}}(X)\) is the part of the potential of \(X\) that is determined inside the subtree (made precise in the proof of Lemma 7.4); the sums run over the subsets \(X\) of that subtree in each of three states of its top vertex \(v\): in state \(1\), \(v\in X\); in state \(2\), \(v\notin X\) and some child of \(v\) lies in \(X\); in state \(3\), \(v\notin X\) and no child of \(v\) lies in \(X\). For \(P,Q\in\mathbb{R}^3\) let \[\tag{17} P\circ Q=\Bigl(P_1(2Q_1+Q_2+Q_3),\ \ P_2\bigl(Q_1+Q_2+\tfrac{Q_3}2\bigr)+P_3Q_1,\ \ P_3\bigl(Q_2+\tfrac{Q_3}2\bigr)\Bigr),\] and let \(\mathrm{fin}(P)=P_1+P_2+\tfrac12P_3\) and \(\mathrm{Init}_y(j)=\bigl(\tfrac y2,0,2^{-j}\bigr)\) for integers \(j\ge0\); the argument \(j\) of \(\mathrm{Init}_y\) will be the number \(\nu_v\) of vertices owned by \(v\). The operation \(\circ\) is bilinear, and it adds a completed child with message \(Q\) to a partially built message \(P\). For \(y\ge0\), order the children of every vertex arbitrarily, and for \(v\in V(F)\) with children \(w_1,\dots,w_d\) in this order define the messages from the leaves upwards by \[\tag{18} \mathrm{msg}_v=\Bigl(\cdots\bigl(\mathrm{Init}_y(\nu_v)\circ\mathrm{msg}_{w_1}\bigr)\circ\cdots\Bigr)\circ\mathrm{msg}_{w_d}.\] The output of this recursion is as follows.
Lemma 7.4 (Tree recursion). Let \(y\ge0\), and let the messages \(\mathrm{msg}_v\) be defined by (18) for any order of the children. Then every \(\mathrm{msg}_v\) has nonnegative entries and \(W_{F,\nu}(y)=\mathrm{fin}(\mathrm{msg}_r)\).
Lean proof: triple_single, triple_split, treeW_eq_fin (formalisation)
7.4 Antinorm certificates in the cumulative cone
The third step bounds \(\mathrm{fin}(\mathrm{msg}_r)\) from below for all trees at once. The idea is to find a convex region that the merge operation maps into itself up to a known scale; the scale then multiplies along the tree. The region must be closed upwards in an order that the recursion respects. Let \[\mathcal K_{\mathrm{cum}}=\bigl\{P\in\mathbb{R}^3:\ P_1\ge0,\ P_1+P_2\ge0,\ P_1+P_2+P_3\ge0\bigr\},\] the cumulative cone. It is the preimage of \(\mathbb{R}^3_{\ge0}\) under the cumulative map \(P\mapsto(P_1,P_1+P_2,P_1+P_2+P_3)\), so it is a convex cone generated by \((1,-1,0)\), \((0,1,-1)\) and \((0,0,1)\), and it contains \(\mathbb{R}^3_{\ge0}\). For a finite nonempty set \(Z\subseteq\mathbb{R}^3_{\ge0}\) let \(\mathcal P_Z=\mathrm{conv}(Z)+\mathcal K_{\mathrm{cum}}\) and \(c_Z=\min_{z\in Z}\mathrm{fin}(z)\). The facts about \(\mathcal K_{\mathrm{cum}}\) that the certificate argument uses (Lemma D.4.1) and the abstract mechanism behind it (Lemma D.4.2), which Section 8 reuses with another cone, are proved in Appendix D.4.
The next lemma is the core of the third step. If a finite set \(Z\) of nonnegative messages is such that \(\mathcal P_Z\) absorbs the merge of any two of its generators and contains every initial message up to a geometric scale, then that scale multiplies along any tree. Data \((y,e_1,e_2,Z)\) with these two properties are the certificates referred to above.
Lemma 7.5 (Antinorm certificate). Let \(y\ge0\) and \(e_1,e_2>0\), and let \(Z\subseteq\mathbb{R}^3_{\ge0}\) be finite and nonempty with
(a) \(z\circ z'\in\mathcal P_Z\) for all \(z,z'\in Z\), and
(b) \(\mathrm{Init}_y(j)\in e_1e_2^{\,j}\,\mathcal P_Z\) for every integer \(j\ge0\).
Then for every tree \(F\) with \(s\) vertices and every \(\nu:V(F)\to\mathbb Z_{\ge0}\), writing \(\nu(F)=\sum_{v\in V(F)}\nu_v\), we have \(W_{F,\nu}(y)\ge c_Z\,e_1^{\,s}e_2^{\,\nu(F)}\). If \(e_2\le1\), then (b) holds for all \(j\) as soon as it holds for \(j\le j_0\) and \((y/2,0,0)\in e_1e_2^{\,j_0+1}\mathcal P_Z\).
Lean proof: merge_mem_smul_PZ, init_all, triple_D_mem, tree_bound_of_certificate (formalisation)
Together with Lemma 7.3, a certificate turns into the exponential-moment condition of the main theorem.
Corollary 7.6 (From certificates to exponential moments). Suppose that \((y,e_1,e_2,Z)\) satisfies the hypotheses of Lemma 7.5. Then for every connected graph \(G\) and every connected dominating set \(S\) of \(G\) with \(|S|=s\), writing \(\sigma=s/n\), \[W_S(y)\ge c_Z\,e_1^{\,s}e_2^{\,n-s} \qquad\text{and}\qquad \max_{0\le t\le s}\frac{\mu_t(S)}{\binom nt}\ \ge\ c_Z\,2^{-n\,\psi_{\mathrm{cert}}(\sigma)},\] where \(\psi_{\mathrm{cert}}(\sigma)=\log(1+y)-\sigma\log e_1-(1-\sigma)\log e_2\).
So a certificate gives condition (\(\star\)) of Theorem 3.5 for \(S\) with the rate \(\psi=\psi_{\mathrm{cert}}(\sigma)\) and the loss factor \(\Gamma=\max(1,1/c_Z)\); we call \(\psi_{\mathrm{cert}}\) the rate function of the certificate.
7.5 The certificates and the coverage of the solution fraction
Two certificates for Lemma 7.5 cover the middle range of the solution fraction; the closed form of Section 6 covers the rest. We record the certificates first and then combine the two arguments.
Proposition 7.7 (Antinorm certificates). For \(i\in\{0,1\}\), the data \((y_i,e_{1,i},e_{2,i},Z_i)\) of certificate \(i\) (Appendix F.2) are rational and satisfy the hypotheses of Lemma 7.5, with \(j_0=30\) and \(e_{2,i}<1\):
| \(i\) | \(y_i\) | \(e_{1,i}\) | \(e_{2,i}\) | \(|Z_i|\) | \(c_{Z_i}\ge\) | \(\psi_i(\sigma)\) |
|---|---|---|---|---|---|---|
| \(0\) | \(\frac{69}{200}\) | \(\frac{747593601}{960952792}\) | \(\frac{512099210}{652701491}\) | \(27\) | \(0.6212\) | \(0.7776061742+0.0122113367\,\sigma\) |
| \(1\) | \(\frac{17}{50}\) | \(\frac{248231700}{312721579}\) | \(\frac{568097827}{739289481}\) | \(29\) | \(0.6293\) | \(0.8022330021-0.0468085913\,\sigma\) |
Here \(\psi_i\) is the rate function \(\psi_{\mathrm{cert}}\) of Corollary 7.6, with coefficients rounded to ten decimals. The two lines cross at \(\sigma_\times=0.4172629270\ldots\), and \[\max\Bigl(\max_{\sigma\in[0.31,\,0.4172629]}\psi_0(\sigma),\ \max_{\sigma\in[0.4172629,\,0.54]}\psi_1(\sigma)\Bigr) =0.78270151357\ldots<\psi^* .\]
Lean proof: cert0_Z, cert0_pairs, cert0_inits, cert1_Z, cert1_pairs, cert1_inits, tree_bound_of_checks, rstheta_tree_bound_0, rstheta_tree_bound_1, rst_rates, rst_rates_detail (formalisation) · Certificates: cert_final_0.json, cert_final_1.json, verify_cert.py, verify_cert_indep.py, v_cert_primal.py, cz_bounds.py, rst_rate_interval.py
Proof. The hypotheses of Lemma 7.5 are finitely many conditions on the rational data; they are checked for both certificates in Appendix F.2. Since \(\psi_i\) is linear in \(\sigma\), its maximum on an interval is attained at an endpoint, so the displayed maximum is the largest of the values of \(\psi_0\) at \(0.31\) and \(0.4172629\) and of \(\psi_1\) at \(0.4172629\) and \(0.54\); these four values are bounded from above in Appendix F.2, and each is below \(0.78270152<\psi^*\). ∎
| range of \(\sigma=s/n\) | argument | certified exponent |
|---|---|---|
| \((0,0.31]\) | closed form (Corollary 6.2, Proposition 6.1(c)) | \(F^*(\sigma)\le0.7807\) |
| \([0.31,0.4172629]\) | certificate \(0\) | \(\psi_0(\sigma)\le0.78270152\) |
| \([0.4172629,0.54]\) | certificate \(1\) | \(\psi_1(\sigma)\le0.78270152\) |
| \([0.54,1]\) | closed form (Corollary 6.2, Proposition 6.1(c)) | \(F^*(\sigma)\le0.7802\) |
The cases of Table 3 combine into condition (\(\star\)) for every connected dominating set.
Proposition 7.8 (Rate of RS-\(\theta\)). For every connected graph \(G\) and every connected dominating set \(S\) of \(G\), \[\max_{0\le t\le|S|}\frac{\mu_t(S)}{\binom nt}\ \ge\ \frac{2^{-\psi^*n}}{2} .\]
Lean proof: rst_rate (formalisation) · Certificates: rst_rate_interval.py
Proof. Let \(s=|S|\) and \(\sigma=s/n\); we follow Table 3.
Closed form: \(\sigma\notin[0.31,0.54]\). By Corollary 6.2 and Proposition 6.1(c), \(\max_t\mu_t(S)/\binom nt\ge2^{-nF^*(\sigma)}/2\ge2^{-0.7807n}/2\ge2^{-\psi^*n}/2\), as \(0.7807<\psi^*\).
Certificates: \(\sigma\in[0.31,0.54]\). Take \(i=0\) if \(\sigma\le0.4172629\) and \(i=1\) otherwise. Corollary 7.6 and Proposition 7.7 give \(\max_t\mu_t(S)/\binom nt\ge c_{Z_i}2^{-n\psi_i(\sigma)}\ge0.62\cdot2^{-\psi^*n}\ge2^{-\psi^*n}/2\). ∎
Proof of Theorem 7.2. We verify the hypotheses of Lemma 5.2. For each \(s\), RS-\(\theta\) is Algorithm MLS-\(\theta\) for \(\Phi_{\mathrm{CDS}}\), \(\mathcal{A}_{\mathrm{St}}\) and \(g(X)=|\mathrm{T}(J_X)|\), with \(k=s\), \(\psi=\psi^*\), \(\Gamma=2\) and confidence \(\kappa\). By Corollary 5.8, \(\mathcal{A}_{\mathrm{St}}\) solves \(\Phi_{\mathrm{CDS}}\)-Extension in polynomial space and \(g\) is a running-time exponent for it, and the parameters are constants. So Theorem 3.5 applies: the run for \(s\) takes time \(2^{\psi^*n}n^{O(1)}\) and polynomial space, and it rejects if \(\gamma_{\mathrm{c}}(G)>s\). For \(s=\gamma_{\mathrm{c}}(G)\) let \(S\) be a minimum connected dominating set; Proposition 7.8 gives condition (\(\star\)) for \(S\) with \(\Gamma=2\), so \(s\) is accepted with probability at least \(1-e^{-\kappa}\). Finally, \(2^{\psi^*}=2^{0.7827016}=1.7203\ldots<1.7204\). ∎
7.6 A lower bound for RS-\(\theta\): uniform lobsters
The analysis above is close to tight for Algorithm RS-\(\theta\) itself. Recall that a caterpillar is a tree that becomes a path when its leaves are deleted, and a lobster is a tree that becomes a caterpillar when its leaves are deleted. The uniform \((2,2)\)-lobster \(\Lambda_L\) has a spine path \(x_1x_2\cdots x_L\); every spine vertex has exactly two neighbors off the spine, its legs, and every leg has exactly two further neighbors, both of degree \(1\), its claws. So the legs are the vertices at distance \(1\) from the spine, the claws are the vertices at distance \(2\) and the leaves of \(\Lambda_L\), and \(n=7L\). The proposition identifies the minimum solution of \(\Lambda_L\), bounds the acceptance probability of RS-\(\theta\) on it in terms of the normalized moments, and bounds these moments by a certificate.
Proposition 7.9 (Uniform \((2,2)\)-lobsters). Let \(L\ge1\), let \(n=7L\) be the number of vertices of \(\Lambda_L\), and let \(S^*\) be the set of its spine vertices and legs. Then:
(a) \(S^*\) is the unique minimum connected dominating set of \(\Lambda_L\); so \(\gamma_{\mathrm{c}}(\Lambda_L)=3L\) and \(\sigma=3/7\).
(b) Run Algorithm RS-\(\theta\) with any rate \(\psi\ge0\) in place of \(\psi^*\) (and the corresponding cap and trial counts). For \(s=\gamma_{\mathrm{c}}(\Lambda_L)\), the probability that \(s\) is accepted is at most \(P_{\mathrm{nec}}\,2^{\psi n}\max_t\mu_t(S^*)/\binom nt\), where \(P_{\mathrm{nec}}\le n^{O(1)}\) is the polynomial factor of Proposition 3.10 (with \(\Gamma=2\)).
(c) For all \(L\ge1\) and \(0\le t\le n\), \(\mu_t(S^*)/\binom nt\le(n+1)\,1.71927^{-n}\). Conversely, \(\min_t\binom nt/\mu_t(S^*)\le C\cdot1.71928^{n}\) for a constant \(C\) and all \(L\ge1\). So \(\bigl(\min_t\binom nt/\mu_t(S^*)\bigr)^{1/n}\) lies in \([1.71927,1.71928]\) up to factors \((n+1)^{1/n}\) and \(C^{1/n}\); numerically its limit is \(1.7192725\ldots\), attained near \(y^*=0.3453\) in the generating-function form.
Consequently, RS-\(\theta\) run with a rate \(\psi\) in place of \(\psi^*\) outputs \(\gamma_{\mathrm{c}}(\Lambda_L)\) with probability bounded away from \(0\) on all \(\Lambda_L\) only if \(2^{\psi}\ge1.71927\); so the certified base \(1.7204\) exceeds the least base with which this algorithm succeeds on all \(\Lambda_L\) by at most \(0.0012\).
Lean, partial: u_eq, M_mulVec, lobster_lower, lobster_upper, Lam, Sstar, lobW_eq_matrix, mu_mul_pow_le_W, pow_le_choose_mul, lob_moments_upper, lob_moments_lower, rst_caterpillar_c, rst_caterpillar_c_of_agree (formalisation) · Certificates: lobster_rate_certificate.py
The proposition holds for every graph whose unique maximum-leaf spanning tree is \(\Lambda_L\) with \(L\ge2\) (Appendix D.4.3; parts (b) and (c) with their proofs verbatim, part (a) by a separate argument), so the lower bound does not rest on instances on which Max Leaf Spanning Tree is easy.