4 Corollaries: mean exponents, linear savings and product form
This section derives earlier and intermediate forms of Monotone Local Search from Theorem 3.5: the mean-exponent theorem (Section 4.1), which is the reference point of the black-box barrier (Section 9) and of the comparisons in Section 11; a closed form for linear mean savings (Section 4.2), used for Algorithm RS (Section 6); and multivariate Monotone Local Search, for whose product-form running-time exponents the main theorem certifies no smaller bound (Section 4.3). Appendix C explains why Max Leaf Spanning Tree needs sample-dependent running times.
Recall the notation of Section 3: \(\Phi\) is an implicit set system, \(I\) an instance with \(N=|I|\), universe \(U_I\) with \(n=|U_I|\le N\) and solution family \(\mathcal{F}_I\); the algorithm \(\mathcal{A}\) solves \(\Phi\)-Extension with running-time exponent \(g\) (Definition 3.2); and for \(S\in\mathcal{F}_I\) with \(|S|=k\) the exponential moments and the generating function are \[\mu_t(S)=\sum_{X\in\binom{S}{t}}2^{-g(I,X,k)}\quad(0\le t\le k),\qquad W_S(y)=\sum_{t=0}^{k}\mu_t(S)\,y^t\quad(y\ge0),\] as in Definition 3.3. By the first inequality of Lemma 3.9, the generating-function condition \(W_S(y)\ge(1+y)^n2^{-\psi n}/\Gamma\), for a single \(y\ge0\), implies condition (\(\star\)) of Theorem 3.5, and by the second inequality the converse holds up to a factor \(n+1\): with \[M(S)=\min_{0\le t\le k}\frac{\binom nt}{\mu_t(S)}\qquad\text{and}\qquad G(S)=\inf_{y\ge0}\frac{(1+y)^n}{W_S(y)},\] we have \(M(S)\le G(S)\le(n+1)M(S)\). Note that (\(\star\)) holds exactly when \(2^{\psi n}\Gamma\ge M(S)\); thus, with \(\Gamma=1\), \(M(S)\) is the smallest running-time bound \(2^{\psi n}\) (up to the factor \(N^{O(1)}\)) that Theorem 3.5 certifies for the solution \(S\), and \(G(S)\) is the smallest one that the generating-function condition certifies. The binary entropy \(H\) and the entropy estimates (1) are as in Section 3.1.
4.1 Mean exponents: the Markov cutoff
The simplest hypothesis on a sample-dependent running-time exponent is a bound \(\lambda\) on its mean over the \(t\)-subsets of a solution, for one sample size \(t\). We derive the resulting bound from the main theorem by Jensen’s inequality; Remark 4.2 describes the direct algorithm, the Markov-cutoff mechanism of Lemma 2 of Zamir (Zamir 2023), which discards samples whose running-time exponent exceeds \(\lambda\) by more than one.
In Theorem 4.1, \(t(I,k)\) is the sample size and \(\lambda(I,k)\) the bound on the mean running-time exponent of samples of this size inside a solution of size \(k\); the running time is the expected number \(\binom nt/\binom kt\) of uniform \(t\)-sets drawn until one lies inside a fixed solution, times the running-time bound \(2^{\lambda(I,k)}\) of an extension call at the mean running-time exponent.
Theorem 4.1 (Mean-exponent Monotone Local Search). Let \(t(I,k)\in\{0,\dots,k\}\) and \(\lambda(I,k)\ge0\) be computable in time \(N^{O(1)}\), with values \(\lambda(I,k)\le N^{O(1)}\), such that for every instance \(I\), every \(k\le n\) and every \(S\in\mathcal{F}_I\) with \(|S|=k\), writing \(t=t(I,k)\), \[\tag{5} \mathbb{E}_X\bigl[g(I,X,k)\bigr]\le\lambda(I,k),\qquad X\text{ uniform in }\binom{S}{t}.\] Then there is a randomized algorithm that, given \(I\) and \(k\le n\), runs in time \[\frac{\binom nt}{\binom kt}\,2^{\lambda(I,k)}\,N^{O(1)}\] and in space \(N^{O(1)}\) plus the space of \(\mathcal{A}\). It answers no if \(\mathcal{F}_I\) contains no set of size at most \(k\), and it answers yes with probability at least \(1-1/e\) if \(\mathcal{F}_I\) contains a set of size exactly \(k\). Running it for \(k=0,1,\dots,n\) decides \(\Phi\)-Subset as in Remark 3.6.
Lean, partial: mu_ge_of_mean, mls_success_of_mean (formalisation)
Proof. Fix \(I\) and \(k\), and write \(t=t(I,k)\) and \(\lambda=\lambda(I,k)\). If \(n=0\), then \(\mathcal{F}_I\subseteq\{\emptyset\}\) and \(k=0\), and the membership test for \(\mathcal{F}_I\) decides the question in time \(N^{O(1)}\). So let \(n\ge1\). Define \(\psi\) by \[2^{\psi n}=\frac{\binom nt}{\binom kt}\,2^{\lambda},\] and take \(\Gamma=1\) and \(\kappa=1\). Since \(\binom kt\le\binom nt\le2^n\) and \(\binom kt\ge1\), we have \(0\le\psi\le1+\lambda/n\le N^{O(1)}\), and \(\psi\) is computable from \((I,k)\) in time \(N^{O(1)}\) because \(t\) and \(\lambda\) are. Let \(S\in\mathcal{F}_I\) with \(|S|=k\). The function \(x\mapsto2^{-x}\) is convex, so Jensen’s inequality and (5) give \[\mu_t(S)=\binom kt\,\mathbb{E}_X\bigl[2^{-g(I,X,k)}\bigr]\ \ge\ \binom kt\,2^{-\mathbb{E}_X[g(I,X,k)]} \ \ge\ \binom kt\,2^{-\lambda}=\binom nt\,2^{-\psi n},\] with \(X\) uniform in \(\binom St\). Hence (\(\star\)) holds with \(\Gamma=1\), and Theorem 3.5 gives the time and space bounds, soundness, and success probability \(1-e^{-1}\). ∎
Remark 4.2 (The Markov cutoff). The algorithm of this proof is Algorithm MLS-\(\theta\), which tries every sample size and every threshold. A direct algorithm uses only the sample size \(t=t(I,k)\) and the single threshold \(\lambda+1\), where \(\lambda=\lambda(I,k)\): it repeats the following trial \(m=\lceil(\lambda+1)\binom nt\binom kt^{-1}\rceil\) times and answers no if no trial succeeds. A trial draws \(X\) uniformly from \(\binom{U_I}{t}\), computes \(g(I,X,k)\), and, if \(g(I,X,k)\le\lambda+1\) (with a rational threshold in \([\lambda+1,\lambda+2]\) if needed, Remark 3.7), runs \(\mathcal{A}\) on \((I,X,k)\) and answers yes if \(\mathcal{A}\) accepts. Every yes answer is correct, each trial takes time \(2^{\lambda+2}N^{O(1)}\), so the total time is the bound of the theorem, and the space is that of \(\mathcal{A}\) plus \(N^{O(1)}\). For completeness, let \(S\in\mathcal{F}_I\) with \(|S|=k\). A trial has \(X\subseteq S\) with probability \(\binom kt/\binom nt\); conditioned on this event \(X\) is uniform in \(\binom St\), and by Markov’s inequality and (5) the running-time exponent exceeds \(\lambda+1\) with probability at most \(\lambda/(\lambda+1)\). Otherwise the trial runs \(\mathcal{A}\), which accepts because \(Y=S\setminus X\) extends \(X\) to \(S\). So a trial succeeds with probability at least \(p_{\mathrm{trial}}=\binom kt/((\lambda+1)\binom nt)\ge1/m\), and all \(m\) trials fail with probability at most \((1-p_{\mathrm{trial}})^m\le e^{-1}\). This is the Markov-cutoff mechanism of Lemma 2 of Zamir (Zamir 2023).
4.2 Linear mean savings
In many applications the bound on the mean running-time exponent of a sample decreases roughly linearly in the number of sampled elements: for samples \(X\) of size \(t\) inside a solution of size \(k\), the mean of \(g(I,X,k)\) is at most \(\beta n-\rho t+C\) for reals \(\beta,\rho,C\ge0\), so that each sampled element of the solution lowers this bound by \(\rho\). The next corollary gives the resulting exponent of the running time in closed form. At solution fraction \(\sigma=k/n\), a uniformly random element lies in a fixed solution with probability \(\sigma\), so each further sampled element divides the probability that the sample lies inside the solution by about \(1/\sigma\). This multiplies the number of trials by about \(1/\sigma\); in exchange it divides the running-time bound \(2^{\beta n-\rho t+C}\) of an extension call by \(2^{\rho}\). We show (Corollary 4.3(2)) that sampling lowers the exponent exactly when \(\rho>\log(1/\sigma)\).
For \(\sigma\in(0,1)\), reals \(\beta,\rho\ge0\) and \(p=2^{-\rho}\) define \[\tag{6} F^*(\sigma)= \begin{cases} \beta & \text{if }\sigma\le p,\\[2pt] \beta+\sigma\log\dfrac p\sigma+(1-\sigma)\log\dfrac{1-p}{1-\sigma}=\beta-\sigma\rho+H(\sigma)+(1-\sigma)\log(1-p) & \text{if }\sigma>p . \end{cases}\] For \(\sigma>p\) the corresponding base is \[2^{F^*(\sigma)}=2^{\beta}\left(\frac p\sigma\right)^{\sigma}\left(\frac{1-p}{1-\sigma}\right)^{1-\sigma} \le2^{\beta}\left(\sigma\cdot\frac p\sigma+(1-\sigma)\cdot\frac{1-p}{1-\sigma}\right)=2^{\beta}\] by the weighted arithmetic–geometric mean inequality, with equality only if \(p/\sigma=(1-p)/(1-\sigma)\), that is \(\sigma=p\). So \(F^*(\sigma)\le\beta\), with equality exactly when \(\sigma\le p\).
In the corollary, \(\beta n+C\) bounds the mean running-time exponent of the unsampled call (\(t=0\)), \(\rho\) is the decrease of this bound per sampled element, and \(C\) is an additive slack.
Corollary 4.3 (Linear mean savings). Let \(\beta=\beta(I,k)\), \(\rho=\rho(I,k)\) and \(C=C(I,k)\) be nonnegative reals computable from \((I,k)\) in time \(N^{O(1)}\), with \(\beta n+C\le N^{O(1)}\). Let \(I\) be an instance and \(k\) an integer with \(\sigma=k/n\in(0,1)\) such that for every \(t\in\{0,\dots,k\}\) and every \(S\in\mathcal{F}_I\) with \(|S|=k\), \[\tag{7} \mathbb{E}_X\bigl[g(I,X,k)\bigr]\le\beta n-\rho t+C,\qquad X\text{ uniform in }\binom St .\] Let \(F^*(\sigma)\) be as in (6), and let \(\kappa>0\) be as in Theorem 3.5. Then:
(1) Every such \(S\) satisfies \(G(S)\le2^{C+nF^*(\sigma)}\). Algorithm MLS-\(\theta\) with \(\Gamma=1\), confidence \(\kappa\) and a rate computable from \((I,k)\) in time \(N^{O(1)}\) gives a randomized algorithm that, given \(I\) and \(k\), runs in time \(2^{\max(0,\,C+nF^*(\sigma))}N^{O(1)}\), answers no if \(\mathcal{F}_I\) contains no set of size at most \(k\), and answers yes with probability at least \(1-e^{-\kappa}\) if \(\mathcal{F}_I\) contains a set of size \(k\).
(2) \(F^*(\sigma)<\beta\) if and only if \(\rho>\log(1/\sigma)\).
Lean, partial: linear_savings_W, one_sample_size (formalisation)
The corollary uses the bound (7) for every \(t\), and \(\rho\) only has to be the decrease of a bound on the mean running-time exponent over the samples inside a solution, not a decrease of the running-time exponent guaranteed for every sampled element. Remark 4.4 compares this with the algorithm of Theorem 4.1 at a single sample size.
The proof is in Appendix D.2.1. It bounds the moments \(\mu_t(S)\) from below by Jensen’s inequality, as in the proof of Theorem 4.1, sums them by the binomial theorem, and minimizes the resulting bound on \((1+y)^n/W_S(y)\) over \(y\); the minimum lies at \(y=0\) if \(\sigma\le p\) and at \(y_0=(\sigma-p)/(1-\sigma)\) otherwise.
Remark 4.4 (One sample size). The algorithm of Theorem 4.1 at a single sample size \(t\) with the mean bound \(\beta n-\rho t+C\) of (7) runs in time \(\binom nt\binom kt^{-1}2^{\beta n-\rho t+C}N^{O(1)}\), and \[\tag{8} \binom nt\binom kt^{-1}2^{\beta n-\rho t}=2^{\beta n}\prod_{i=0}^{t-1}\frac{n-i}{2^{\rho}(k-i)} .\] The factor with index \(i\) weighs the two effects of sampling one more element: the probability that the sample lies inside a fixed solution of size \(k\) is divided by \((n-i)/(k-i)\), and the running-time bound \(2^{\beta n-\rho t+C}\) of the extension call is divided by \(2^{\rho}\). As \(n\ge k\), the factors are nondecreasing in \(i\), and with \(p=2^{-\rho}\) the factor with index \(i\) is below \(1\) exactly when \((1-p)i<k-pn\). So the best sample size is the number of factors below \(1\), and sampling at all beats \(t=0\) exactly when the first factor \(n/(2^{\rho}k)=p/\sigma\) is below \(1\), that is \(\sigma>p\), the condition of Corollary 4.3(2).
By the entropy estimates (1), the running time above is at most \((k+1)2^{C}2^{nf_\sigma(\tau)}N^{O(1)}\) with \(\tau=t/n\) and \[\tag{9} f_\sigma(\tau)=H(\tau)-\sigma H(\tau/\sigma)+\beta-\rho\tau\qquad(0\le\tau\le\sigma),\qquad p=2^{-\rho}.\] Expanding the entropies gives \(H(\tau)-\sigma H(\tau/\sigma)=-(1-\tau)\log(1-\tau)+(\sigma-\tau)\log(\sigma-\tau)-\sigma\log\sigma\), so on \([0,\sigma)\) the derivative is \(f_\sigma'(\tau)=\log\frac{1-\tau}{\sigma-\tau}-\rho\), the logarithm of the factor of (8) with index \(i=\tau n\). It is strictly increasing in \(\tau\), so \(f_\sigma\) is convex on \([0,\sigma]\). If \(\sigma\le p\) (which includes \(\rho=0\)), then \(f_\sigma'(\tau)\ge f_\sigma'(0)=\log\frac1\sigma-\rho\ge0\), and the minimum of \(f_\sigma\) over \([0,\sigma]\) is \(f_\sigma(0)=\beta=F^*(\sigma)\). If \(\sigma>p\) (so \(p<1\)), then \(f_\sigma'\) vanishes exactly at \(\tau^*=\frac{\sigma-p}{1-p}\in(0,\sigma)\), the unique minimizer. With \(A=\frac{1-\sigma}{1-p}\) we have \(1-\tau^*=A\), \(\sigma-\tau^*=pA\) and \(-\rho=\log p\), so \[f_\sigma(\tau^*)=-(1-p)A\log A+pA\log p+\tau^*\log p-\sigma\log\sigma+\beta =\beta+\sigma\log\frac p\sigma+(1-\sigma)\log\frac{1-p}{1-\sigma}=F^*(\sigma),\] using \((1-p)A=1-\sigma\) and \(pA+\tau^*=\sigma\). In both cases the minimum of \(f_\sigma\) over \([0,\sigma]\) is \(F^*(\sigma)\). Since \(H(\tau)-\sigma H(\tau/\sigma)\) is nondecreasing on \([0,\sigma]\) (its derivative is \(\log\frac{1-\tau}{\sigma-\tau}\ge0\)), the single-size algorithm run at \(t=\lfloor\tau^*n\rfloor\) (with \(\tau^*=0\) if \(\sigma\le p\)) attains the exponent \(C+nF^*(\sigma)\) of Corollary 4.3(1) up to the factors \(2^{\rho}\) and \(k+1\). Algorithm RS (Section 6), the black-box barrier (Appendix D.6) and the two-class family of Appendix A use \(f_\sigma\) in this form.
Lean, partial: one_sample_size (formalisation)
4.3 Product-form running times and multivariate Monotone Local Search
In the classical forms of Monotone Local Search the running-time bound of the extension algorithm depends on the sample \(X\) only through \(|X|\). (Fomin et al. 2019) showed that an extension algorithm running in time \(c^{k-|X|}N^{O(1)}\) on input \((I,X,k)\) gives a randomized algorithm for \(\Phi\)-Subset running in time \((2-1/c)^nN^{O(1)}\); Gaspers and Lee (Gaspers and Lee 2017) allowed a further factor \(b^{\,n-|X|}\) in the running time of the extension algorithm and obtained the running time \((1+b-1/c)^nN^{O(1)}\); and the multivariate version, with a further factor \(d^{|X|}\), gives \((b+d-d/c)^nN^{O(1)}\) when \(d\le bc\) (Corollary 4.6). We now derive all three from the main theorem and show that for such running-time exponents the main theorem certifies no smaller running-time bound.
For constants \(b,c,d\ge1\), the product-form running-time exponent is \[\tag{10} g(I,X,k)=(n-|X|)\log b+(k-|X|)\log c+|X|\log d .\] It is nonnegative on inputs with \(k\ge|X|\), the domain of Definition 3.2, because \(b,c,d\ge1\). Put \[\mathrm{base}(b,c,d)=b+\min(d,bc)\Bigl(1-\frac1c\Bigr)= \begin{cases}b+d-d/c&\text{if }d\le bc,\\ bc&\text{if }d\ge bc.\end{cases}\] Since \(b+d-d/c-bc=(c-1)(d-bc)/c\), also \(\mathrm{base}(b,c,d)=\min(b+d-d/c,\,bc)\). If \(S\in\mathcal{F}_I\) with \(|S|=k\) and \(g\) has the form (10) on all inputs \((I,X,k)\) with \(X\subseteq S\), then every \(X\in\binom St\) has \(2^{g(I,X,k)}=b^{\,n-t}c^{\,k-t}d^{\,t}\), so \[\tag{11} \mu_t(S)=\binom kt\,b^{-(n-t)}c^{-(k-t)}d^{-t}\qquad(0\le t\le k).\] Thus \(M(S)\) and \(G(S)\) depend only on \(n\), \(k\), \(b\), \(c\) and \(d\); we write \(M_k\) and \(G_k\) for them (with \(n,b,c,d\) fixed), and define them by (11) for every integer \(0\le k\le n\).
The evaluation of the product form through a generating function goes back to Gaspers and Lee (Gaspers and Lee 2017) and (Fomin et al. 2019) (see Section 1.3). The generating function \(W_S\) used here is a different series, but for product-form running times it has the following closed form.
Proposition 4.5 (Product form). Let \(b,c,d\ge1\), let \(0\le k\le n\), and let \(\mu_t\), \(M_k\) and \(G_k\) be given by (11). Then:
(a) The generating function is \(W(y)=\sum_{t=0}^{k}\mu_ty^t=b^{-n}c^{-k}(1+ybc/d)^k\), and \[M_k=\min_{0\le t\le k}\frac{\binom nt}{\binom kt}\,b^{\,n-t}c^{\,k-t}d^{\,t} .\]
(b) \(M_k\le G_k\le \mathrm{base}(b,c,d)^n\). More precisely, \(y^*=(c-1)d/(bc)\) gives \((1+y^*)^n/W(y^*)=(b+d-d/c)^n\), and \(y=0\) gives \((1+0)^n/W(0)=b^nc^k\le(bc)^n\).
(c) Conversely, the following hold:
if \(c=1\), then \(G_0=M_0=b^n=\mathrm{base}(b,c,d)^n\);
if \(c>1\) and \(d<bc\), let \(\sigma^*=cd/(bc+cd-d)\); then \(\sigma^*\in(0,1)\); if \(\sigma^*n\) is an integer, then \(G_{\sigma^*n}=(b+d-d/c)^n\); and for every \(n\ge1\), \[\max_{0\le k\le n}G_k\ \ge\ (b+d-d/c)^n\Bigl(\frac{b}{b+d-d/c}\Bigr)^{1/\sigma^*};\]
if \(c>1\) and \(d\ge bc\), then \(G_n=M_n=(bc)^n=\mathrm{base}(b,c,d)^n\).
Consequently, with \(\mathsf K=\bigl((b+d-d/c)/b\bigr)^{1/\sigma^*}\) in the second case and \(\mathsf K=1\) otherwise, \[\frac{\mathrm{base}(b,c,d)^n}{(n+1)\mathsf K}\ \le\ \max_{0\le k\le n}M_k\ \le\ \mathrm{base}(b,c,d)^n .\]
The expression for \(M_k\) in (a) is the classical Monotone Local Search expression. So for product-form running-time exponents, \(\max_{0\le k\le n}M_k\), the smallest running-time bound \(2^{\psi n}\) that Theorem 3.5 with \(\Gamma=1\) certifies for every solution size, is \(\mathrm{base}(b,c,d)^n\) up to the factor \((n+1)\mathsf K\), where \(\mathsf K\) depends only on \(b,c,d\).
Proof. Parts (a) and (b) are direct computations. For (c) we treat the solution size as a real parameter \(x\): the minimization over \(y\) in (a) then defines a concave function \(\mathsf f\) of \(x\), whose value at \(x=\sigma^*n\) is exactly \(n\log(b+d-d/c)\), and concavity transfers this value to the integer \(\lfloor\sigma^*n\rfloor\), losing in \(G_{\lfloor\sigma^*n\rfloor}\) only the factor \(\mathsf K\), which does not depend on \(n\).
(a) Grouping by \(t\) and using the binomial theorem, \[W(y)=\sum_{t=0}^{k}\binom kt y^t\,b^{-(n-t)}c^{-(k-t)}d^{-t} =b^{-n}c^{-k}\sum_{t=0}^{k}\binom kt\Bigl(\frac{ybc}{d}\Bigr)^t=b^{-n}c^{-k}\Bigl(1+\frac{ybc}{d}\Bigr)^k .\] The formula for \(M_k=\min_t\binom nt/\mu_t\) is immediate from (11).
(b) The inequality \(M_k\le G_k\) is the first inequality of Lemma 3.9: for every \(y\ge0\), \(W(y)\le(1+y)^n/M_k\). At \(y^*\ge0\) we have \(1+y^*bc/d=c\), so \(W(y^*)=b^{-n}\) and \[\frac{(1+y^*)^n}{W(y^*)}=\bigl(b(1+y^*)\bigr)^n=\Bigl(b+\frac{(c-1)d}{c}\Bigr)^n=\Bigl(b+d-\frac dc\Bigr)^n .\] At \(y=0\) the ratio is \(1/W(0)=b^nc^k\le(bc)^n\), because \(c\ge1\) and \(k\le n\). Hence \(G_k\le\min(b+d-d/c,\,bc)^n=\mathrm{base}(b,c,d)^n\).
Part (c) and the final inequalities are proved in Appendix D.2.2. ∎
With the product form evaluated, the multivariate theorem follows; its cases \(d=1\) and \(b=d=1\) are the two classical statements. In the running-time bound \(b^{\,n-|X|}c^{k-|X|}d^{|X|}N^{O(1)}\) of the extension algorithm, \(b\) is the factor per element outside the sample, \(c\) the factor per element that may still be added, and \(d\) the factor per sampled element.
Corollary 4.6 (Multivariate Monotone Local Search). Let \(b,c,d\ge1\) be constants such that \(\log b\), \(\log c\) and \(\log d\) are computable to polynomially many bits in polynomial time. If \(\Phi\)-Extension can be solved in time \(b^{\,n-|X|}c^{k-|X|}d^{|X|}N^{O(1)}\) on every input \((I,X,k)\), then \(\Phi\)-Subset can be decided by a randomized algorithm with one-sided error at most \(1/e\) in time \[\Bigl(b+\min(d,bc)\Bigl(1-\frac1c\Bigr)\Bigr)^nN^{O(1)}= \begin{cases}(b+d-d/c)^nN^{O(1)}&\text{if }d\le bc,\\ (bc)^nN^{O(1)}&\text{if }d\ge bc,\end{cases}\] and in space \(N^{O(1)}\) plus the space of the extension algorithm.
If the extension algorithm returns a completion when it accepts, the algorithm returns a solution. As \(bc\ge1\), the case \(d=1\) gives \((1+b-1/c)^nN^{O(1)}\), the theorem of Gaspers and Lee (Gaspers and Lee 2017), and the case \(b=d=1\) gives \((2-1/c)^nN^{O(1)}\), the randomized theorem of (Fomin et al. 2019). The case \(d\ge bc\) needs no sampling: a single call of the extension algorithm with \(X=\emptyset\) takes time \(b^nc^kN^{O(1)}\le(bc)^nN^{O(1)}\).
Proof. The product-form exponent (10) is nonnegative, computable in time \(N^{O(1)}\), and by hypothesis a running-time exponent for the given extension algorithm. Fix \(k\le n\), and put \(2^{\psi}=\mathrm{base}(b,c,d)\), \(\Gamma=1\) and \(\kappa=1\); then \(0\le\psi\le\log(bc)\) is a constant (if \(\log b\), \(\log c\) or \(\log d\) is irrational, \(g\) is rounded up as in Remark 3.7, which replaces \(\Gamma\) by \(2\); if \(\psi\) is irrational, a rational rate in \([\psi,\psi+1/n]\) is used; both change the running time by a constant factor). Let \(S\in\mathcal{F}_I\) with \(|S|=k\). On the inputs \((I,X,k)\) with \(X\subseteq S\) the running-time exponent has the form (10), so \(W_S\) is the function \(W\) of Proposition 4.5(a), and by Proposition 4.5(b) the generating-function condition holds with \(2^{\psi n}=\mathrm{base}(b,c,d)^n\): at \(y=y^*\) if \(d\le bc\), and at \(y=0\) if \(d\ge bc\). By the first inequality of Lemma 3.9, \(S\) satisfies (\(\star\)). So Theorem 3.5 gives an algorithm that runs in time \(\mathrm{base}(b,c,d)^nN^{O(1)}\), answers no if \(\mathcal{F}_I\) has no set of size at most \(k\), and answers yes with probability at least \(1-1/e\) if \(\mathcal{F}_I\) has a set of size \(k\). Running it for \(k=0,\dots,n\) decides \(\Phi\)-Subset as claimed (Remark 3.6). A witness \(Y\) returned by the extension algorithm gives the solution \(X\cup Y\). For \(d=1\) we have \(\min(1,bc)=1\), since \(bc\ge1\), so \(\mathrm{base}(b,c,1)=1+b-1/c\); for \(b=d=1\) this is \(2-1/c\). ∎
Max Leaf Spanning Tree.
For Max Leaf Spanning Tree, the extension problem that the original Monotone Local Search needs is W[1]-hard. Product-form running-time exponents certify nothing below a single unsampled call when \(k/n\le d/(bc)\), nor, when \(c=1\), for the worst solution size. Both statements and their proofs are in Appendix C.