8 Closure sampling under exponential moments: Algorithm RSC
The analysis of Section 7 is nearly tight for its algorithm, and the instances on which it is nearly attained have a common feature: some vertices of the solution have many neighbors inside the solution. A random sample of the solution then contains several neighbors of such a vertex, and the vertex stands out among the vertices with at least two sampled neighbors. Algorithm RSC adds each such candidate to the sample independently with a small probability, before it computes the number of terminals and decides whether to call the Steiner tree algorithm. The probability is graded: a candidate with exactly two sampled neighbors is added with probability \(p_2\), a candidate with three or more with probability \(p_3\ge p_2\). The main theorem in its budgeted-trial form (Theorem 3.14) applies to these trials directly, and the exponential moment in its success condition becomes an average over the random closure as well as over the sample. For \((p_2,p_3)=(0.07,0.077)\) we prove the following bound, the best one in this paper.
Theorem 8.1 (Algorithm RSC). For every constant \(\kappa>0\), Algorithm RSC (Algorithm 8.2) runs in time \(O^{*}\bigl(\varrho^{\,n}\bigr)\), where \(\varrho=1.6990\ldots<1.6991\), and in polynomial space, on every connected graph \(G\) with \(n\) vertices. 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.6991^n)\) and polynomial space.
Lean, partial: rsc_success, rsc_success_of_bound, rsc_success_of_data, rsc_maxLeaf_of_data, rsc_rho_lt, Wcl_eq (formalisation)
The proof of the value of \(\varrho\) rests on Proposition D.5.23. The base is \(\varrho=(1+y)/\hat e\) for the rationals \(y=31/100\) and \(\hat e=145729958/189014575\) of the certificate, so the running time is \(2^{\psi n}n^{O(1)}\) with \(\psi=\log\varrho=0.76476681\ldots\).
Route of the proof.
Section 8.1 describes the algorithm, and Section 8.2 shows that Theorem 3.14 reduces Theorem 8.1 to a lower bound \(W^{\mathrm{cl}}_S(y)\ge0.6060\,\hat e^n\) on a generating function \(W^{\mathrm{cl}}_S\) of the closure trials (Definition 8.3), for every minimum connected dominating set \(S\). We prove this lower bound (Proposition 8.6) by extending the analysis of Section 7 in three steps.
(1) Tree model (Appendix D.5.1). Lemma D.5.2 replaces the graph by a spanning tree \(F\) of \(G[S]\), keeping for every vertex outside \(S\) a factor \(h_u\) that records whether it is dominated and whether it was a candidate, and keeping of the closure only what \(F\) certifies. Every outside vertex is assigned to an owner in \(S\) (Definition D.5.3), and Lemma D.5.4 compares \(h_u\) with a factor of the owner; the comparison depends on the type of \(u\), that is, on whether \(u\) has two or more neighbors in \(S\). Most factors \(h_u\) are then bounded below by owner factors times an exposure, a factor \(q_\tau=1-p_\tau\) whenever the owner is in the closed sample, together with a credit \(\varpi_\tau\ge1\) on the factor of an owner outside the closed sample, which records that an exposed vertex is usually dominated by one of its other neighbors (Lemma D.5.13). For the other shared vertices, Jensen’s inequality gives a correction term instead (Lemma D.5.6), which the pointwise comparison bounds from below.
(2) Light owners (Appendices D.5.2 and D.5.3). The tree model is evaluated by a ten-state recursion along \(F\) (Lemma D.5.8). Inequalities between the coordinates of its messages (Lemma D.5.9) show that the Jensen correction of an outside vertex is nonnegative when its owner has few owned vertices and small degree in \(F\) (Lemma D.5.11), and they bound the odds that a vertex of \(S\) is sampled from below (Lemma D.5.12), which is what the credits rest on. The other owners are exposed; minimality of \(S\) limits the exposures at the leaves of \(F\) (Lemma D.5.14).
(3) Certificate (Appendix D.5.4). An antinorm in an eight-dimensional poset cone, in the style of Lemma 7.5, bounds a relaxation of the recursion from below for every tree that can arise (Lemma D.5.20); the relaxation (Lemma D.5.18) forgets whether a vertex has more than two sampled children except where the eight states can tell, and it never overestimates the tree model. The certificate consists of \(1024\) rational points and staged conditions for exposed vertices, and Proposition D.5.23 states the conditions it satisfies.
The three steps are carried out in Appendix D.5, and Section 8.3 records how tight the analysis is and how the parameters were chosen.
Proof map.
Table 4 lists the ingredients of Theorem 8.1, with the kind of argument behind each and the machine checks that exist for it.
| Ingredient | Statements | Argument | Machine checks |
|---|---|---|---|
| Steiner extension in time \(2^{|\mathrm{T}(J_X)|}n^{O(1)}\) and polynomial space | Lemmas 5.3 and 5.6 and Corollary 5.8 | inclusion–exclusion over branching walks (Nederlof 2013); proofs in Appendix D.3 | Lean: the computed value, not running time or space |
| Budgeted trials: running time, rejection, success probability | Theorem 3.14, Lemma 8.4 and Corollary 8.5 | mathematical proof | Lean: rejection and success probability, not running time |
| Graph to tree model, owners, exposures, credits, ten-state recursion, light owners | Lemma D.5.2 to Corollary D.5.17 | mathematical proof | Lean |
| Finitely many conditions imply the bound for every tree | Lemmas D.5.18, D.5.19 and D.5.20 | invariant region and induction from the leaves | Lean |
| Light pairs (condition (C3)) and credit inequalities | Lemmas D.5.21 and D.5.22 | rational bounds on logarithms | exact program; Lean |
| Certificate data: (C1), (C2), (C4), (C5), (C6) and \(c_Z>0.6060\) | Proposition D.5.23 | \(1024\) rational points and about \(3.7\) million relations, each checked exactly | two independently written programs, exact rational arithmetic; Lean with compiled evaluation |
| Base \(\varrho<1.6991\) | proof of Theorem 8.1 | comparison of rationals | Lean |
| Max Leaf Spanning Tree from Connected Dominating Set | Lemma 5.1 | mathematical proof | Lean |
Apart from the Lean kernel, the bound therefore rests on the mathematical proofs of the running time and space bounds, including those of the Steiner extension, which are not formalized, and on the two programs that check the data of the certificate; the Lean check of these data (Appendix F.9) is a third check, which also trusts the Lean compiler. The two programs are independent: the second was written from the definitions of this section without reusing code of the first, it re-derives the recursion, and it rejects perturbed copies of the certificate (Appendix F.4).
Throughout this section \(0<p_2\le p_3<\frac12\), \(q_2:=1-p_2\) and \(q_3:=1-p_3\), so \(q_2\ge q_3>\frac12\); for an integer \(k\ge2\) we write \(p_k:=p_2\) if \(k=2\) and \(p_k:=p_3\) if \(k\ge3\), and \(q_k:=1-p_k\). For a connected graph \(G\) with vertex set \(V\) and \(X'\subseteq V\) the candidate set is \[C(X')=\bigl\{v\in V\setminus X':\ |N(v)\cap X'|\ge2\bigr\}.\] With \(p_2=p_3\) the closure is the Bernoulli closure of a single probability; the bound of the theorem rests on the graded one (see Remark 8.7).
Esmer and Kulik (Esmer and Kulik 2025) also use problem-specific random steps before a black-box call, for parameterized approximation of vertex deletion problems: each of their sampling steps returns a vertex whose removal lowers the optimum with at least a fixed probability, and the running time of the black-box call is fixed by the algorithm. Here the closure is added to a uniform sample inside Monotone Local Search, its probabilities depend on the sample, and it changes the running-time exponent of the call, which the exponential moments account for.
8.1 The algorithm
How RSC decides.
For each candidate size \(s\), RSC runs the trials of RS-\(\theta\) (Algorithm 7.1), indexed by a sample size \(t\in\{0,\dots,s\}\) and an integer threshold \(\theta\), with one change, which takes polynomial time per trial: after drawing a uniform \(t\)-set \(X'\), it puts each candidate \(v\in C(X')\) into a set \(\Upsilon\) independently with probability \(p_{|N(v)\cap X'|}\), that is, with probability \(p_2=0.07\) if \(v\) has exactly two sampled neighbors and \(p_3=0.077\) if it has more, and it then treats the closed sample \(X=X'\cup\Upsilon\) as RS-\(\theta\) treats its sample, also discarding \(X\) if \(|X|>s\). Fix a solution \(S\). The closure never increases the number of terminals (Lemma D.5.1), and an added candidate with a neighbor outside \(N[X']\) lowers it; but the closed sample leaves \(S\) when the closure adds a vertex outside \(S\), which happens with probability \(1-\prod_{v\in C(X')\setminus S}q_{|N(v)\cap X'|}\). The small values of \(p_2\) and \(p_3\) keep this probability small; the analysis needs small probabilities, and \(p_3\) only slightly above \(p_2\).
Algorithm 8.2 (RSC). a connected graph \(G\) with \(n\ge1\) vertices. \(p_2=0.07\), \(p_3=0.077\), \(y=31/100\) and \(\hat e=145729958/189014575\); \(\psi=\log\varrho\) with \(\varrho=(1+y)/\hat e\); a constant \(\kappa>0\) and \(\Gamma=2\); a cap \(\Theta\) and trial counts \(m_{t,\theta}\) within the ranges (2). For \(s=1,2,\dots,n\), decide whether to accept \(s\) as follows, and output the first accepted \(s\) (and \(n\) if there is none). For every \(t\in\{0,\dots,s\}\) and every integer \(\theta\in\{0,\dots,\Theta\}\), repeat \(m_{t,\theta}\) times:
(a) draw \(X'\) uniformly from \(\binom Vt\) and compute \(C(X')\);
(b) put each \(v\in C(X')\) into \(\Upsilon\) independently with probability \(p_{|N(v)\cap X'|}\), and let \(X=X'\cup\Upsilon\);
(c) if \(|X|\le s\) and \(|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\le\theta\), compute \(\operatorname{OPT}(J_X)\) by Corollary 5.8, and accept \(s\) if \(\operatorname{OPT}(J_X)\le s-|X|\).
The trial counts \(m_{t,\theta}\) should not be confused with the numbers \(\nu_v\) of owned vertices used in the analysis.
8.2 Applying the budgeted-trials theorem
The trials of RSC are not those of Algorithm MLS-\(\theta\): the extension algorithm is called on the closed sample \(X'\cup\Upsilon\), whose distribution is not uniform on sets of a given size. The budgeted form of the main theorem (Theorem 3.14) needs only that a trial of threshold \(\theta\) runs in time \(2^\theta n^{O(1)}\), rejects if no solution of size at most \(k\) exists, and accepts whenever a random variable attached to it is at most \(\theta\). The exponential moment in its success condition is then a generating function that averages over the closure.
Definition 8.3 (Closure generating function). Let \(G\) be a connected graph, \(S\) a connected dominating set of \(G\), \(0\le p_2\le p_3\le1\) and \(y\ge0\). For \(X'\subseteq V\) let \(\Upsilon\) be the random subset of \(C(X')\) that contains each candidate \(v\) independently with probability \(p_{|N(v)\cap X'|}\). Put \[W^{\mathrm{cl}}_S(y)=\sum_{X'\subseteq S}y^{|X'|}\, \mathbb{E}_\Upsilon\Bigl[\mathbf 1[\Upsilon\subseteq S]\,2^{-|\mathrm{T}(J_{X'\cup\Upsilon})|}\Bigr].\]
For \(p_2=p_3=0\) the set \(\Upsilon\) is empty and \(W^{\mathrm{cl}}_S\) is the generating function \(W_S\) of (15).
Lemma 8.4 (The trials of RSC). Let \(G\) be a connected graph with \(n\) vertices and let \(1\le s\le n\). For \(t\in\{0,\dots,s\}\) and an integer \(\theta\ge0\), let \(\mathrm{Tr}_{t,\theta}\) be one execution of steps (a)–(c) of Algorithm 8.2 for \(s\), with any rational \(0\le p_2\le p_3\le1\).
(a) \(\mathrm{Tr}_{t,\theta}\) runs in time \(2^\theta r_0(n)\) and space \(r_0(n)\) for a polynomial \(r_0\) that depends only on \(p_2\) and \(p_3\), not on \(G\), \(s\), \(t\) or \(\theta\), and it rejects if \(\gamma_{\mathrm{c}}(G)>s\).
(b) Let \(S\) be a connected dominating set of \(G\) with \(|S|=s\). Let \(\xi_t=|\mathrm{T}(J_X)|\) if \(X\subseteq S\) and \(\xi_t=\infty\) otherwise, where \(X=X'\cup\Upsilon\) is the closed sample of the trial. Then the distribution of \(\xi_t\) does not depend on \(\theta\), \(\Pr[\mathrm{Tr}_{t,\theta}\text{ accepts}]\ge\Pr[\xi_t\le\theta]\) for every \(\theta\), and \(W^{\mathrm{cl}}_S(y)\le(1+y)^n\max_{0\le t\le s}\mathbb{E}\bigl[2^{-\xi_t}\bigr]\) for every \(y\ge0\).
Lean, partial: rsc_trials_T2, rsc_trials_T3, rsc_trials_W (formalisation)
Proof. (a) Steps (a) and (b) and the test in (c) take polynomial time, by the convention on random draws in Section 3.1, since \(p_2\) and \(p_3\) are rational. The Steiner extension is called only if \(|\mathrm{T}(J_X)|\le\theta\), and then it takes time \(2^{|\mathrm{T}(J_X)|}n^{O(1)}\le2^\theta n^{O(1)}\) and polynomial space by Corollary 5.8, where the exponent of \(n\) is a fixed constant. Together these give one polynomial \(r_0\) as stated. If the trial accepts, then some \(Y\subseteq V\setminus X\) with \(|Y|\le s-|X|\) makes \(X\cup Y\) a connected dominating set, by the description of the solutions of \(J_X\) in Section 5; this set has at most \(s\) vertices.
(b) The trial’s random choices do not involve \(\theta\). Suppose that \(\xi_t\le\theta\). Then \(X\subseteq S\), so \(|X|\le s\) and \(|\mathrm{T}(J_X)|\le\theta\); the trial computes \(\operatorname{OPT}(J_X)\), and since \(X\cup(S\setminus X)=S\) is a connected dominating set, \(S\setminus X\) is a solution of \(J_X\) and \(\operatorname{OPT}(J_X)\le|S\setminus X|=s-|X|\). So the trial accepts. For the last inequality, \(X\subseteq S\) holds if and only if \(X'\subseteq S\) and \(\Upsilon\subseteq S\), and \(X'\) is uniform in \(\binom Vt\), so \[\mathbb{E}\bigl[2^{-\xi_t}\bigr]=\binom nt^{-1}\sum_{X'\in\binom Vt}\mathbf 1[X'\subseteq S]\, \mathbb{E}_\Upsilon\Bigl[\mathbf 1[\Upsilon\subseteq S]\,2^{-|\mathrm{T}(J_{X'\cup\Upsilon})|}\Bigr].\] Grouping the terms of Definition 8.3 by \(t=|X'|\) (only \(t\le s\) occur) and using \(\sum_{t=0}^n\binom nty^t=(1+y)^n\) gives \(W^{\mathrm{cl}}_S(y)=\sum_{t=0}^s\binom nt\mathbb{E}[2^{-\xi_t}]\,y^t\le(1+y)^n\max_t\mathbb{E}[2^{-\xi_t}]\). ∎
The following corollary of Theorem 3.14 and Lemma 5.2 packages the wrapper around budgeted trials for connected dominating sets.
Corollary 8.5 (Budgeted trials for connected domination). Let \(\psi\ge0\) be a real constant that can be approximated to within \(2^{-b}\) in time \(b^{O(1)}\) for every integer \(b\ge1\), let \(\Gamma_n\ge1\) be computable in time \(n^{O(1)}\) with \(\Gamma_n\le n^{O(1)}\), and let \(\kappa>0\) be a constant. Suppose that there are a randomized algorithm \(\mathrm{Tr}\) with inputs \((G,s,t,\theta)\), written \(\mathrm{Tr}_{t,\theta}\) when \(G\) and \(s\) are fixed, and a polynomial \(r_0\) such that for every connected graph \(G\) with \(n\) vertices, every \(s\in\{1,\dots,n\}\), every \(t\in\{0,\dots,s\}\) and every integer \(\theta\ge0\):
(T1) \(\mathrm{Tr}_{t,\theta}\) runs in time \(2^\theta r_0(n)\) and space \(r_0(n)\),
(T2) \(\mathrm{Tr}_{t,\theta}\) rejects if \(\gamma_{\mathrm{c}}(G)>s\), and
(T3) if \(s=\gamma_{\mathrm{c}}(G)\), then there are random variables \(\xi_t\) with values in \([0,\infty]\), whose distributions do not depend on \(\theta\), such that \(\Pr[\mathrm{Tr}_{t,\theta}\text{ accepts}]\ge\Pr[\xi_t\le\theta]\) for all \(t\) and \(\theta\), and \(\max_{0\le t\le s}\mathbb{E}[2^{-\xi_t}]\ge2^{-\psi n}/\Gamma_n\).
Then the algorithm that, for \(s=1,\dots,n\) in turn, runs Algorithm 3.13 on \((G,s)\) with the index set \(\{0,\dots,s\}\), these trials, rate \(\psi\), loss factor \(\Gamma_n\), confidence \(\kappa\) and a cap and trial counts within the ranges (2), and outputs the first accepted \(s\), or \(n\) if none, runs in time \(2^{\psi n}n^{O(1)}\) and polynomial space, never outputs a value below \(\gamma_{\mathrm{c}}(G)\), outputs \(\gamma_{\mathrm{c}}(G)\) with probability at least \(1-e^{-\kappa}\), and, when \(n\ge3\), solves Max Leaf Spanning Tree within the same bounds.
Lean, partial: cds_budgeted, cds_budgeted_maxLeaf (formalisation)
Proof. Fix \(s\). The cap and the trial counts are computed in polynomial time: the number \(x=\psi n+\log\Gamma_n\) of (2) is approximated to within \(\frac12\), and \(M_{t,\theta}=4\kappa\Gamma_n(\Theta+1)2^{\psi n-\theta}\) to within a factor \(2\), by rationals obtained from an approximation of \(\psi\) and from \(\Gamma_n\), which suffices, as noted after (2); the values of \(\psi\), \(\Gamma_n\) and \(\kappa\) are at most \(n^{O(1)}\). Extend \(\mathrm{Tr}\) to all other inputs, that is, to instances that do not encode a connected graph and to values of \(s\) or \(t\) outside the ranges above, by rejecting at once after a test that takes time \(r_1(N)\) for a polynomial \(r_1\). We may take \(r_0\) nondecreasing; as \(n\le N\), conditions (T1) and (T2) of Theorem 3.14 then hold for every instance and every \(k\le n\), with the polynomial \(r_0+r_1\) and space bound \(\mathrm{sp}=0\). By Theorem 3.14 for the implicit set system \(\Phi_{\mathrm{CDS}}\) of Definition 5.7, with \(k=s\), the index sets \(\mathcal{T}_{I,k}=\{0,\dots,k\}\) (empty for \(k<0\)), which are listed in time \(O(N)\), the run for \(s\) takes time \(2^{\psi n}n^{O(1)}\) and polynomial space by (T1), rejects if \(\gamma_{\mathrm{c}}(G)>s\) by (T2), and, when \(s=\gamma_{\mathrm{c}}(G)\), accepts with probability at least \(1-e^{-\kappa}\) by (T3), with a minimum connected dominating set as the set \(S\) of size \(k\) in Theorem 3.14. Lemma 5.2, with success probability \(1-e^{-\kappa}\), gives the rest, the total time being \(n\cdot2^{\psi n}n^{O(1)}\). ∎
The analysis uses the solution \(S\) only through \(W^{\mathrm{cl}}_S\), and it needs \(S\) to be a minimum connected dominating set. The proof of the following proposition, given at the end of Appendix D.5.4 in Appendix D.5, uses the certificate of Proposition D.5.23.
Proposition 8.6 (Closure generating function of a minimum solution). Let \(p_2=0.07\), \(p_3=0.077\), \(y=31/100\) and \(\hat e=145729958/189014575\). For every connected graph \(G\) with \(n\) vertices and every connected dominating set \(S\) of \(G\) with \(|S|=\gamma_{\mathrm{c}}(G)\), \[W^{\mathrm{cl}}_S(y)\ \ge\ 0.6060\,\hat e^n .\]
Lean, partial: rsc_bound_of_data, rsc_bound_of_data', rsc_bound_trials (formalisation)
Proof of Theorem 8.1, given Proposition 8.6. The steps of Algorithm 8.2 for \(s\) are Algorithm 3.13 with the trials \(\mathrm{Tr}_{t,\theta}\) of Lemma 8.4, rate \(\psi=\log\varrho\), loss factor \(\Gamma_n=2\) and confidence \(\kappa\), so Theorem 8.1 follows from Corollary 8.5, with \(n\le2\) handled directly; the rate \(\psi\), the logarithm of a rational number, can be approximated to any precision in polynomial time. Properties (T1) and (T2) are Lemma 8.4(a). For (T3), let \(s=\gamma_{\mathrm{c}}(G)\), let \(S\) be a minimum connected dominating set, and take the variables \(\xi_t\) of Lemma 8.4(b); their distributions do not depend on \(\theta\) and \(\Pr[\mathrm{Tr}_{t,\theta}\text{ accepts}]\ge\Pr[\xi_t\le\theta]\), and by Lemma 8.4(b) and Proposition 8.6, \[\max_{0\le t\le s}\mathbb{E}\bigl[2^{-\xi_t}\bigr]\ \ge\ \frac{W^{\mathrm{cl}}_S(y)}{(1+y)^n} \ \ge\ 0.6060\Bigl(\frac{\hat e}{1+y}\Bigr)^n=0.6060\cdot2^{-\psi n}\ \ge\ \frac{2^{-\psi n}}2 .\] So RSC runs in time \(2^{\psi n}n^{O(1)}=O^{*}(\varrho^n)\) and polynomial space, never outputs a value below \(\gamma_{\mathrm{c}}(G)\), outputs \(\gamma_{\mathrm{c}}(G)\) with probability at least \(1-e^{-\kappa}\), and, for \(n\ge3\) by Corollary 8.5, solves Max Leaf Spanning Tree within the same bounds; for \(n\le2\) the maximum leaf spanning tree is \(G\) itself (Lemma 5.1). Finally \(\varrho=(1+y)/\hat e=1.6990\ldots<1.6991\), by exact evaluation of the rational number \(\frac{131}{100}\cdot\frac{189014575}{145729958}=\frac{990436373}{582919832}\), so \(O^{*}(\varrho^n)\subseteq O(1.6991^n)\). ∎
8.3 Tightness of the analysis
The following remark is a numerical observation; it is not used in the proof of Theorem 8.1.
Remark 8.7 (How tight the analysis is). On the uniform \((2,2)\)-lobster \(\Lambda_L\) of Proposition 7.9, the generating function \(W^{\mathrm{cl}}_S\) of the unique minimum connected dominating set can be evaluated by a transfer matrix. With \((p_2,p_3)=(0.07,0.077)\), the running-time bound \(\inf_{y>0}(1+y)^n/W^{\mathrm{cl}}_S(y)\) that Lemma 8.4 and Theorem 3.14 give is about \(1.6976^n\) (numerical, floating point), so the certified running time \(O(1.6991^n)\) is within a factor \(2^{0.0013n}\) of the best that this route can give for this algorithm. The grading is worth about \(0.0008\) in the base: with \(p_2=p_3=0.07\) an antinorm certificate of the same kind certifies about \(1.6999^n\).
The values of \(p_2\), \(p_3\) and \(y\) come from a numerical exploration, which the following remark records; as with Remark 8.7, nothing in it is used in a proof.
Remark 8.8 (Choice of the closure probabilities). Without closure (\(p_2=p_3=0\)), Algorithm RSC is RS-\(\theta\), which needs time \(\Omega(1.7192^n)\) on the uniform lobsters (Proposition 7.9). A candidate with \(k\) sampled neighbors in different components of the sample can merge up to \(k\) components into one and lower the number of terminals by up to \(k-1\) if it lies in \(S\), whereas the trial is lost if it lies outside \(S\), whatever \(k\) is; this is why a larger probability for candidates with three or more sampled neighbors can pay. The analysis, however, charges a factor \(q_\tau=1-p_\tau\) for every exposed outside vertex, and the light-owner tests of Definition D.5.10 hold only for small probabilities. Numerically, the smallest base that the exact tree model of Appendix D.5 can certify, over \((p_2,p_3,y)\), is attained near \((0.07,0.077,0.31)\), where it is about \(1.6983\); the eight-state relaxation cannot go below about \(1.6985\) there, and the certificate gives \(1.69910\). The window for \(p_3\) is narrow: at \((p_2,p_3)=(0.07,0.15)\), owners of two or more outside vertices fail the test for type-\(3\) vertices and the limit of the tree model rises to about \(1.749\).
The decimal \(1.6991\) needs no numerical slack: \(\varrho=990436373/582919832=1.699095\ldots\) is an exact rational, and every condition of the certificate is checked exactly, so the rounding up to four decimals is the only step between \(\varrho\) and the stated base.