3 Monotone Local Search with sample-dependent running times
This section proves the main theorem, on which the rest of the paper is built. It concerns an extension algorithm whose running time is exponential in a quantity that depends on the sample, and it says that sampling and completing finds a solution quickly as soon as the extension algorithm is fast on enough subsets of a single solution. “Enough” is measured by the sum of \(2^{-x}\), for running time \(2^x\), over the subsets of the solution of a given size, which we call an exponential moment, compared with the number of subsets of the universe of that size.
Section 3.1 fixes the model. Section 3.2 presents Algorithm MLS-\(\theta\), the main theorem and its proof. Sections 3.3, 3.4 and 3.5 show that the condition of the theorem can be phrased through a generating function, that this condition is necessary for the algorithm, and that the algorithm is optimal, up to polynomial factors, among all algorithms that draw uniform samples, run the extension algorithm only on samples whose running-time exponent is at most a chosen threshold, and are charged \(2^\theta\) for a trial with threshold \(\theta\). Section 3.6 gives the general form that later sections use: budgeted trials, which include one-sided-error extension algorithms. Appendix B compares the main theorem with restart strategies, the Markov cutoff and earlier uses of exponential moments. Appendix A treats arbitrary samplable distributions and records which further changes of the trials can and cannot lower the running time by more than a polynomial factor. The mean-exponent theorem, linear mean savings and multivariate Monotone Local Search are derived from Theorem 3.5 in Section 4.
3.1 Setting
We write \(\log\) for the logarithm to base \(2\) and \(\ln\) for the natural logarithm. For a finite set \(S\) and an integer \(t\), \(\binom St\) is the family of \(t\)-element subsets of \(S\). For a statement or event \(A\), \(\mathbf 1[A]\) is \(1\) if \(A\) holds and \(0\) otherwise. We write \(0^0=1\) and \(0\log0=0\). For \(x\in[0,1]\), \(H(x)=-x\log x-(1-x)\log(1-x)\) is the binary entropy, so that \(2^{H(x)}=x^{-x}(1-x)^{-(1-x)}\). We use the standard entropy estimates for binomial coefficients, valid for integers \(0\le j\le m\): \[\tag{1} \frac{2^{mH(j/m)}}{m+1}\;\le\;\binom mj\;\le\;2^{mH(j/m)} .\] Throughout the paper, \(O^{*}(f)\) denotes \(f\cdot N^{O(1)}\), where \(N\) is the length of the input. Every decimal base of a running time of ours is rounded up from a constant that the analysis proves to be strictly smaller, so the polynomial factors are absorbed and we write \(O(c^n)\). Exact and parametric bases of ours, such as \(1.8^n\), \(2^{n/2}\) or \(c^k\), are stated with the \(O^{*}\)-notation. So are the two bases of ours that are only computed numerically, the mean-exponent bound for Graph Motif after Theorem 11.13 and the multivariate bound for Max Leaf Spanning Tree in Appendix C.2; no proof uses them. A randomized algorithm with one-sided error never answers yes on a no-instance; its error probability is the probability of answering no on a yes-instance. We assume that a randomized algorithm can draw a uniform integer from \(\{1,\dots,M\}\) in time polynomial in \(\log M\); so it draws a uniform \(t\)-element subset of an \(n\)-element set, or a Bernoulli variable with a rational probability, in time polynomial in \(n\) or in the bit length of the probability. (With fair coins alone, such draws take this time in expectation but not in the worst case.)
The framework is that of (Fomin et al. 2019): a problem is given by a polynomial-time membership test for its solutions.
Definition 3.1 (Implicit set systems). An implicit set system \(\Phi\) assigns to every instance \(I\in\{0,1\}^*\) a universe \(U_I\) with \(n:=|U_I|\le N:=|I|\) and a family \(\mathcal{F}_I\subseteq2^{U_I}\), such that \(U_I\) can be listed and membership in \(\mathcal{F}_I\) decided in time \(N^{O(1)}\). The members of \(\mathcal{F}_I\) are the solutions of \(I\).
\(\Phi\)-Subset: given \(I\), decide whether \(\mathcal{F}_I\neq\emptyset\).
\(\Phi\)-Extension: given \(I\), a set \(X\subseteq U_I\) and an integer \(k\ge0\), decide whether some \(Y\subseteq U_I\setminus X\) with \(|Y|\le k-|X|\) satisfies \(X\cup Y\in\mathcal{F}_I\), that is, whether \(X\) lies in a solution with at most \(k\) elements. For \(k<|X|\) the answer is no; the extension algorithms of this paper reject such inputs in polynomial time, and their running-time bounds are stated for \(k\ge|X|\).
All theorems below are stated for the decision versions. If the extension algorithm returns a witness \(Y\) when it accepts, the algorithms below return the solution \(X\cup Y\).
Sample-dependent running-time exponents.
In classical and multivariate Monotone Local Search (Corollary 4.6) the running-time bound of an extension call depends on the sample \(X\) only through \(|X|\); Section 1 explains why such a bound gains nothing from sampling for Connected Dominating Set. The model below bounds the running time of the extension algorithm on each input separately, by a function that the subset algorithm can evaluate in advance.
Definition 3.2 (Running-time exponent). Let \(\mathcal{A}\) be an algorithm for \(\Phi\)-Extension. A running-time exponent for \(\mathcal{A}\) is a function \(g\) from inputs \((I,X,k)\) with \(k\ge|X|\) to \([0,\infty)\) such that \(g(I,X,k)\) can be computed in time \(N^{O(1)}\) and \(\mathcal{A}\) runs in time \(2^{g(I,X,k)}N^{O(1)}\) on every such input \((I,X,k)\).
The running-time bound must hold on every input, including samples \(X\) that are contained in no solution. A product-form running-time exponent is \(g(I,X,k)=(n-|X|)\log b+(k-|X|)\log c+|X|\log d\) with constants \(b,c,d\ge1\); it depends on \(X\) only through \(|X|\), and it expresses the running-time bound \(b^{n-|X|}c^{k-|X|}d^{|X|}N^{O(1)}\) of classical and multivariate Monotone Local Search. An example of a sample-dependent running-time exponent is one computed from the number of Steiner terminals that a sample of vertices leaves (Section 5). Once \(I\) and a target size \(k\) are fixed, we write \(g(X)=g(I,X,k)\) for \(|X|\le k\).
Comparisons with thresholds.
The algorithms below compare \(g(I,X,k)\) with thresholds that are integers or rationals of polynomial bit length, and Definition 3.2 guarantees that such a comparison is decided in time \(N^{O(1)}\). This holds for all running-time exponents of this paper.
The main theorem needs, for one solution, the following sums.
Definition 3.3 (Exponential moments and generating function). Fix an instance \(I\), a running-time exponent \(g\), and a solution \(S\in\mathcal{F}_I\) with \(|S|=k\). For \(0\le t\le k\) and real \(y\ge0\) let \[\mu_t(S)=\sum_{X\in\binom St}2^{-g(I,X,k)},\qquad W_S(y)=\sum_{t=0}^k\mu_t(S)\,y^t=\sum_{X\subseteq S}y^{|X|}\,2^{-g(I,X,k)} .\]
If \(X\) is drawn uniformly from \(\binom{U_I}t\), then \(\mu_t(S)/\binom nt=\mathbb{E}\bigl[\mathbf 1[X\subseteq S]\,2^{-g(I,X,k)}\bigr]\): the normalized moment is the expected value of \(2^{-g}\) on the event that the sample lies inside \(S\). Every \(\mu_t(S)\) is positive, because \(g\) is finite, and \(\mu_t(S)\le\binom kt\), because \(g\ge0\).
3.2 The algorithm and the main theorem
How the algorithm works.
The algorithm monitors one quantity: the running-time exponent \(g(I,X,k)\) of each sample \(X\), which it computes in polynomial time before deciding whether to call the extension algorithm. It works through all pairs \((t,\theta)\) of a sample size \(t\in\{0,\dots,k\}\) and an integer threshold \(\theta\ge0\). A trial of the pair \((t,\theta)\) draws a uniformly random \(t\)-set \(X\). If \(g(I,X,k)\le\theta\), the trial runs \(\mathcal{A}\) on \((I,X,k)\), in time \(O^{*}(2^\theta)\); otherwise it discards \(X\) in polynomial time. Low thresholds make trials fast but rarely successful, and high thresholds do the opposite. To balance the two, the algorithm gives every pair the same running-time budget \(O^{*}(2^{\psi n})\), where \(2^{\psi n}\) is the target running time: the pair \((t,\theta)\) receives about \(2^{\psi n-\theta}\) trials. Thresholds above a cap \(\Theta\approx\psi n\) are not used, since a single such trial could exceed the budget. As there are only polynomially many pairs, the total time is \(O^{*}(2^{\psi n})\).
The algorithm has three parameters. The rate \(\psi\ge0\) is the exponent of the target running time \(2^{\psi n}\). The loss factor \(\Gamma\ge1\) weakens the success condition (\(\star\)) of Theorem 3.5 to \(\mu_t(S)\ge\binom nt2^{-\psi n}/\Gamma\), so that an application may prove a lower bound on \(\mu_t(S)\) that is smaller by a factor \(\Gamma\), typically polynomial in \(n\), without changing \(\psi\); the cap and the trial counts grow with \(\Gamma\), and the running time stays \(2^{\psi n}N^{O(1)}\) as long as \(\Gamma\le N^{O(1)}\). The confidence \(\kappa>0\) sets the bound \(e^{-\kappa}\) on the error probability in item (iii) of Theorem 3.5.
Algorithm 3.4 (MLS-\(\theta\)\((\psi,\Gamma,\kappa)\)). an instance \(I\) of \(\Phi\) and an integer \(k\le n\). \(\psi\), \(\Gamma\), \(\kappa\), an integer cap \(\Theta\ge0\) and integer trial counts \(m_{t,\theta}\) such that \[\tag{2} \begin{gathered} x+1\le\Theta\le x+3,\qquad M_{t,\theta}\le m_{t,\theta}\le 2M_{t,\theta}+1,\\ \text{where }x=\psi n+\log\Gamma\text{ and } M_{t,\theta}=4\kappa\Gamma(\Theta+1)\,2^{\psi n-\theta} . \end{gathered}\] For every \(t\in\{0,\dots,k\}\) and every integer \(\theta\in\{0,\dots,\Theta\}\), repeat \(m_{t,\theta}\) times:
1. draw \(X\) uniformly from \(\binom{U_I}t\) and compute \(g(I,X,k)\);
2. if \(g(I,X,k)\le\theta\), run \(\mathcal{A}\) on \((I,X,k)\), and if it accepts, answer yes.
After all trials, answer no.
When \(x\) and \(M_{t,\theta}\) are rational, \(\Theta=\lceil x\rceil+1\) and \(m_{t,\theta}=\lceil M_{t,\theta}\rceil\) qualify. In general, integers in these ranges are computable in time \(N^{O(1)}\) from rational approximations: \(\Theta=\lceil\tilde x+\frac12\rceil+1\) for a rational \(\tilde x\) with \(|\tilde x-x|<\frac12\), and \(m_{t,\theta}=\lceil\hat m\rceil\) for a rational \(\hat m\) with \(M_{t,\theta}\le\hat m\le2M_{t,\theta}\). The ranges in (2) are part of the statement of the theorem, so no separate rounding argument is needed in the applications.
Theorem 3.5 (Exponential-moment Monotone Local Search). Let \(\Phi\) be an implicit set system and let \(\mathcal{A}\) solve \(\Phi\)-Extension with running-time exponent \(g\). Let \(\psi\ge0\), \(\Gamma\ge1\) and \(\kappa>0\) be numbers that can be computed from \((I,k)\) in time \(N^{O(1)}\) and whose values are at most \(N^{O(1)}\). With any cap \(\Theta\) and trial counts \(m_{t,\theta}\) satisfying (2), Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\), given \(I\) and \(k\le n\),
(i) runs in time \(2^{\psi n}N^{O(1)}\) and in space \(N^{O(1)}\) plus the space of \(\mathcal{A}\);
(ii) answers no if \(\mathcal{F}_I\) contains no set of size at most \(k\);
(iii) answers yes with probability at least \(1-e^{-\kappa}\) if \(\mathcal{F}_I\) contains a set \(S\) with \(|S|=k\) that satisfies \[\max_{0\le t\le k}\frac{\mu_t(S)}{\binom nt}\ \ge\ \frac{2^{-\psi n}}{\Gamma}. \tag{$\star$}\]
Condition (\(\star\)) holds in particular if \(W_S(y)\ge(1+y)^n\,2^{-\psi n}/\Gamma\) for some \(y\ge0\).
Lean, partial: mls_sound, mls_success, mls_budget (formalisation)
By items (ii) and (iii), Algorithm MLS-\(\theta\) is a randomized algorithm with one-sided error. Two remarks complete the statement.
Optimization problems.
For an optimization problem, we say that the optimum can be computed (or that the problem can be solved) by a randomized algorithm with one-sided error, with success probability \(p\), if the following holds on every input. On every outcome of its coins, the algorithm stops within the stated time and space bounds. Its output is never better than the optimum, which means never below it for a minimization problem and never above it for a maximization problem. A report that the input has no solution counts as the value \(+\infty\) for a minimization problem and \(-\infty\) for a maximization problem. With probability at least \(p\), the output is the optimum, or a correct report that there is no solution. Where the algorithm also outputs a solution, that solution is feasible on every outcome of the coins and its value is the output value. Unless a statement names another probability, \(p=1-e^{-\kappa}\) for an arbitrary constant \(\kappa>0\) fixed in advance, and the time bound holds for every such \(\kappa\). The wrappers that provide this form are Lemma 5.2, which outputs the first accepted size, Lemma D.11.6, which outputs the least accepted budget, and equivalent loops over the value and the size, such as the one in the proof of Theorem 11.15.
Remark 3.6 (Decision problem). Running the algorithm for \(k=0,1,\dots,n\), with rates \(\psi=\psi(I,k)\), decides \(\Phi\)-Subset with one-sided error at most \(e^{-\kappa}\) in time \(N^{O(1)}\max_k2^{\psi(I,k)n}\), provided every instance with \(\mathcal{F}_I\neq\emptyset\) has a solution \(S\) that satisfies (\(\star\)) with \(k=|S|\).
Remark 3.7 (Real-valued running-time exponents and parameters). If a running-time exponent \(g\) can only be approximated, as the product-form exponent with irrational \(\log b\), \(\log c\) or \(\log d\), replace it by a rational \(\hat g(I,X,k)\) with \(g\le\hat g\le g+1\), computable in time \(N^{O(1)}\) from an approximation of \(g\) to within \(\frac12\). Then \(\hat g\) is again a running-time exponent for \(\mathcal{A}\), and \(2^{-\hat g}\ge2^{-g}/2\), so every exponential moment \(\mu_t(S)\) and every value \(W_S(y)\) of the generating function (Definition 3.3) is at least half of its value for \(g\), and the mean of \(\hat g\) over any set of samples exceeds that of \(g\) by at most \(1\). All statements of the paper therefore hold for \(\hat g\) once their success conditions are weakened accordingly: the loss factor \(\Gamma\) of Theorem 3.5 is replaced by \(2\Gamma\), and an upper bound on the mean running-time exponent of a random sample, as assumed in the mean-exponent theorem (Theorem 4.1), is increased by \(1\). Parameters of the algorithms that are real numbers, such as a bound on the mean or the constants of the affine certificates of Section 9, are likewise replaced by rational approximations from above with slack at most \(1\); this multiplies the running-time bound only by a constant factor.
Proof overview.
The proof has three steps. Running time: the trials of every pair \((t,\theta)\) take time \(2^{\psi n}N^{O(1)}\), because there are about \(2^{\psi n-\theta}\) of them and each takes time at most \(2^\theta N^{O(1)}\). A good threshold exists below the cap: if \(\mu_t(S)\ge\binom nt2^{-\psi n}/\Gamma\), some threshold \(\theta\le\Theta\) is passed by at least \(2^\theta\mu_t(S)/(4(\Theta+1))\) sets \(X\in\binom St\). The sets \(X\in\binom St\) with running-time exponent above the cap contribute at most \(\mu_t(S)/2\) to \(\mu_t(S)\). Success: a trial of that pair succeeds with probability at least \(2^{\theta-\psi n}/(4\Gamma(\Theta+1))\), and the number \(m_{t,\theta}\) of trials of the pair is at least \(\kappa\) divided by this probability. The second step is the following lemma, stated for a general random variable so that Section 3.6 can use it as well. In this section the random variable is the running-time exponent of a uniformly random sample of size \(t\), set to \(\infty\) when the sample is not inside the solution under consideration. We write \(2^{-\infty}=0\).
Lemma 3.8 (Threshold selection). Let \(\xi\) be a random variable with values in \([0,\infty]\) and \(\Pr[\xi<\infty]>0\), so that \(\mathbb{E}[2^{-\xi}]>0\).
(a) If \(\Theta\ge0\) is an integer with \(2^{-\Theta}\le\mathbb{E}[2^{-\xi}]/2\), then some \(\theta\in\{0,\dots,\Theta\}\) satisfies \(\Pr[\xi\le\theta]\,2^{-\theta}\ge\mathbb{E}[2^{-\xi}]/(4(\Theta+1))\).
(b) Conversely, \(\Pr[\xi\le\theta]\,2^{-\theta}\le\mathbb{E}[2^{-\xi}]\) for every integer \(\theta\).
Lean proof: integral_twoPowNeg_pos, threshold_prob, threshold_prob_upper (formalisation)
Proof. (a) On the event \(\xi>\Theta\) we have \(2^{-\xi}<2^{-\Theta}\), so \(\mathbb{E}[2^{-\xi}\mathbf 1[\xi>\Theta]]\le2^{-\Theta}\le\mathbb{E}[2^{-\xi}]/2\) and hence \(\mathbb{E}[2^{-\xi}\mathbf 1[\xi\le\Theta]]\ge\mathbb{E}[2^{-\xi}]/2\). On the event \(\xi\le\Theta\) put \(\theta_\xi=\lceil\xi\rceil\); then \(\theta_\xi\in\{0,\dots,\Theta\}\), because \(0\le\xi\le\Theta\) and \(\Theta\) is an integer. Moreover \(2^{-\xi}<2^{1-\theta_\xi}\) and \(\{\theta_\xi=\theta\}\subseteq\{\xi\le\theta\}\). Hence \[\frac{\mathbb{E}[2^{-\xi}]}2\le\sum_{\theta=0}^{\Theta}2^{1-\theta}\Pr[\xi\le\Theta,\ \theta_\xi=\theta] \le2\sum_{\theta=0}^{\Theta}2^{-\theta}\Pr[\xi\le\theta] \le2(\Theta+1)\max_{0\le\theta\le\Theta}2^{-\theta}\Pr[\xi\le\theta].\]
(b) \(\mathbb{E}[2^{-\xi}]\ge\mathbb{E}[2^{-\xi}\mathbf 1[\xi\le\theta]]\ge2^{-\theta}\Pr[\xi\le\theta]\). ∎
Proof. Throughout, a trial of the pair \((t,\theta)\) is one execution of steps 1 and 2 of Algorithm MLS-\(\theta\) with these values.
(ii) Soundness. If \(\mathcal{A}\) accepts \((I,X,k)\), then \(X\cup Y\in\mathcal{F}_I\) for some \(Y\subseteq U_I\setminus X\) with \(|Y|\le k-t\), and this set has size at most \(t+(k-t)=k\).
(i) Time and space. Drawing \(X\), computing \(g(I,X,k)\) and comparing it with \(\theta\) take time \(N^{O(1)}\). If \(\mathcal{A}\) is run, then \(g(I,X,k)\le\theta\), so the trial takes time \(2^{g(I,X,k)}N^{O(1)}\le2^\theta N^{O(1)}\). The trials of a pair \((t,\theta)\) therefore take time at most \[m_{t,\theta}2^{\theta+1}N^{O(1)}\le\bigl(2M_{t,\theta}+1\bigr)2^{\theta+1}N^{O(1)} \le\bigl(16\kappa\Gamma(\Theta+1)2^{\psi n}+2^{\Theta+1}\bigr)N^{O(1)},\] and \(\Theta\le\psi n+\log\Gamma+3\) gives \(2^\Theta\le8\Gamma2^{\psi n}\). There are \((k+1)(\Theta+1)\) pairs. Since \(\kappa\), \(\Gamma\) and \(\psi\) are at most \(N^{O(1)}\) and \(n\le N\), also \(\Theta+1\le N^{O(1)}\), and the total time is \(2^{\psi n}N^{O(1)}\). Besides the space of \(\mathcal{A}\), the algorithm stores one sample, the current pair and a trial counter of \(O(\Theta+\log(\kappa\Gamma))\) bits.
(iii) Success probability. Let \(S\in\mathcal{F}_I\) with \(|S|=k\) satisfy (\(\star\)), and fix \(t\) with \(\mu_t(S)\ge\binom nt2^{-\psi n}/\Gamma\). Let \(X\) be uniform in \(\binom{U_I}t\), and put \(\xi=g(I,X,k)\) if \(X\subseteq S\) and \(\xi=\infty\) otherwise. Then \(\mathbb{E}[2^{-\xi}]=\mu_t(S)/\binom nt>0\), and for an integer \(\theta\), \(\Pr[\xi\le\theta]=q_\theta/\binom nt\), where \(q_\theta\) is the number of \(X\in\binom St\) with \(g(I,X,k)\le\theta\). The hypothesis of Lemma 3.8(a) holds, because \(\Theta\ge\psi n+\log\Gamma+1\) gives \[2^{-\Theta}\le\frac{2^{-\psi n}}{2\Gamma}\le\frac{\mu_t(S)}{2\binom nt} .\] So some \(\theta\in\{0,\dots,\Theta\}\) satisfies \[p:=\frac{q_\theta}{\binom nt}=\Pr[\xi\le\theta]\ \ge\ \frac{2^\theta\mu_t(S)}{4(\Theta+1)\binom nt} \ \ge\ \frac{2^{\theta-\psi n}}{4\Gamma(\Theta+1)} .\] A trial of the pair \((t,\theta)\) draws an \(X\in\binom St\) with \(g(I,X,k)\le\theta\) with probability \(p\). Then \(\mathcal{A}\) is run on \((I,X,k)\), and it accepts, because \(Y=S\setminus X\) satisfies \(|Y|=k-t\) and \(X\cup Y=S\in\mathcal{F}_I\). The \(m_{t,\theta}\ge M_{t,\theta}=4\kappa\Gamma(\Theta+1)2^{\psi n-\theta}\ge\kappa/p\) trials of this pair are independent, so all of them fail with probability at most \((1-p)^{m_{t,\theta}}\le e^{-pm_{t,\theta}}\le e^{-\kappa}\).
The generating-function condition. For \(y\ge0\), \[W_S(y)=\sum_{t=0}^k\binom nty^t\,\frac{\mu_t(S)}{\binom nt} \le\max_{t}\frac{\mu_t(S)}{\binom nt}\sum_{t=0}^n\binom nty^t =\max_{t}\frac{\mu_t(S)}{\binom nt}\,(1+y)^n,\] so \(W_S(y)\ge(1+y)^n2^{-\psi n}/\Gamma\) implies (\(\star\)). ∎
Mean versus exponential moments.
By Jensen’s inequality, \(\mathbb{E}[2^{-g(X)}]\ge2^{-\mathbb{E}[g(X)]}\) for \(X\) uniform in \(\binom St\), so condition (\(\star\)) is never more demanding than a hypothesis on the mean of \(g\) (Theorem 4.1), and it can certify a smaller running time when \(g\) varies between samples: for Connected Dominating Set it lowers the base from \(1.7449\) to \(1.7204\) (Theorems 6.4 and 7.2). The same inequality, \(\log(1/\mathbb{E}[2^{-\xi}])\le\mathbb{E}[\xi]\), shows that the condition on \(\Theta\) in Lemma 3.8(a) holds whenever \(\Theta\ge\mathbb{E}[\xi]+1\). The converse fails, and the gap can be large: if \(\xi=0\) and \(\xi=2m\) with probability \(\frac12\) each, the condition holds for \(\Theta\ge2\), whereas \(\mathbb{E}[\xi]+1=m+1\).
3.3 The generating function
Condition (\(\star\)) involves a maximum over sample sizes. The generating function \(W_S\) replaces it by an optimization over one real variable, which is how the later sections bound the exponential moments (Sections 7 and 8). The next lemma shows that the two forms agree up to a factor \(n+1\).
Lemma 3.9 (Generating function versus exponential moments). For every instance \(I\), running-time exponent \(g\) and solution \(S\) with \(|S|=k\), the moments \(\mu_t(S)\) with \(0\le t\le k\) are positive, since \(g\) is finite, and \[\min_{0\le t\le k}\frac{\binom nt}{\mu_t(S)}\ \le\ \inf_{y\ge0}\frac{(1+y)^n}{W_S(y)}\ \le\ (n+1)\min_{0\le t\le k}\frac{\binom nt}{\mu_t(S)} .\]
Lean, partial: star_of_W, fw_gf_upper, mu_mul_pow_le_W, pow_le_choose_mul (formalisation)
Proof. The first inequality is the last display of the proof of Theorem 3.5, read as \((1+y)^n/W_S(y)\ge1/\max_t(\mu_t(S)/\binom nt)\); note that \(W_S(y)\ge\mu_0(S)>0\).
For the second, fix \(t\); we exhibit \(y\ge0\) with \((1+y)^n/W_S(y)\le(n+1)\binom nt/\mu_t(S)\), and the minimum over \(t\) gives the claim. If \(t=0\), then \(y=0\) and \((1+y)^n/W_S(y)=1/\mu_0(S)=\binom n0/\mu_0(S)\). If \(0<t<n\), put \(y=t/(n-t)\) and \(\tau=t/n\), so that \(y/(1+y)=\tau\) and \(1/(1+y)=1-\tau\). Since \(W_S(y)\ge\mu_t(S)\,y^t\), \[\frac{(1+y)^n}{W_S(y)}\le\frac{(1+y)^n}{\mu_t(S)\,y^t}=\frac1{\mu_t(S)\,\tau^t(1-\tau)^{n-t}} \le\frac{(n+1)\binom nt}{\mu_t(S)} .\] The last step uses \(\binom nt\tau^t(1-\tau)^{n-t}\ge1/(n+1)\), which holds because \(\tau^t(1-\tau)^{n-t}=2^{-nH(\tau)}\) and \(\binom nt\ge2^{nH(\tau)}/(n+1)\) by (1).
If \(t=n\ge1\), then \(k=n\) and \(y=n\). Now \(W_S(n)\ge\mu_n(S)\,n^n\), and \((1+n)^n/n^n=(1+1/n)^n\le\min(e,2^n)\le n+1\), so \((1+y)^n/W_S(y)\le(n+1)/\mu_n(S)=(n+1)\binom nn/\mu_n(S)\). ∎
The infimum in Lemma 3.9 need not be attained: for \(k=n\) the ratio may decrease toward \(1/\mu_n(S)\) as \(y\to\infty\); Theorem 3.5 uses the generating-function condition only at a specific \(y\).
3.4 The criterion is necessary for the algorithm
Exponential moments are the right quantity for Algorithm MLS-\(\theta\): if the left-hand side of (\(\star\)) is smaller than \(2^{-\psi n}\) by more than a polynomial factor, namely \(4P_{\mathrm{nec}}\) with the polynomial factor \(P_{\mathrm{nec}}\) defined in the next proposition, then the algorithm runs \(\mathcal{A}\) on a subset of \(S\) with probability at most \(1/4\). It might still succeed through another solution, or through a sample that is not inside \(S\); the class-optimality result of Section 3.5 accounts for those as well. Proposition 3.10 is used in Section 7 to show that no analysis of Algorithm RS-\(\theta\) can lower its base below \(1.7192\).
The proposition also covers runs of the algorithm on \((I,k)\) with \(k\) larger than the size of \(S\), which the tightness results of Section 11 need. In such a run, a trial of sample size \(t\) runs \(\mathcal{A}\) on \((I,X,k)\), with the size bound \(k\) rather than \(|S|\). For \(S\in\mathcal{F}_I\), an integer \(k\ge|S|\) and \(0\le t\le|S|\) we therefore put \[\tag{3} \mu^{(k)}_t(S)=\sum_{X\in\binom St}2^{-g(I,X,k)} .\] For \(|S|=k\) this is the exponential moment \(\mu_t(S)\) of Definition 3.3.
Proposition 3.10 (Necessity of (\(\star\))). Let \(k\le n\) be an integer, fix \(S\in\mathcal{F}_I\) with \(|S|\le k\) and run Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\) on \((I,k)\). The expected number of trials that run \(\mathcal{A}\) on a subset of \(S\) is at most \[P_{\mathrm{nec}}\cdot2^{\psi n}\max_{0\le t\le|S|}\frac{\mu^{(k)}_t(S)}{\binom nt},\] where \(P_{\mathrm{nec}}=8\Gamma(k+1)(\Theta+1)\bigl(\kappa(\Theta+1)+1\bigr)\le N^{O(1)}\) and \(\Theta\) is the cap used. In particular, if \(\max_{t\le|S|}\mu^{(k)}_t(S)/\binom nt\le2^{-\psi n}/(4P_{\mathrm{nec}})\), the probability that some trial runs \(\mathcal{A}\) on a subset of \(S\) is at most \(1/4\).
Lean, partial: mls_necessary, Pnec (formalisation)
Proof. A trial of \((t,\theta)\) draws a \(t\)-set \(X\) and runs \(\mathcal{A}\) on \((I,X,k)\) exactly when \(g(I,X,k)\le\theta\). So it runs \(\mathcal{A}\) on a subset of \(S\) exactly when \(t\le|S|\) and it draws \(X\in\binom St\) with \(g(I,X,k)\le\theta\); for \(t>|S|\) this never happens. Let \(t\le|S|\). With \(X\) uniform in \(\binom{U_I}t\) and \(\xi=g(I,X,k)\) if \(X\subseteq S\), \(\xi=\infty\) otherwise, we have \(\mathbb{E}[2^{-\xi}]=\mu^{(k)}_t(S)/\binom nt\), so by Lemma 3.8(b) the event has probability \(\Pr[\xi\le\theta]\le2^\theta\mu^{(k)}_t(S)/\binom nt\). Here \(m_{t,\theta}\le2M_{t,\theta}+1=8\kappa\Gamma(\Theta+1)2^{\psi n-\theta}+1\) and \(2^\theta\le2^\Theta\le8\Gamma2^{\psi n}\) by (2), so \(m_{t,\theta}2^\theta\le8\Gamma(\kappa(\Theta+1)+1)2^{\psi n}\). By linearity of expectation, the expected number of trials that run \(\mathcal{A}\) on a subset of \(S\) is at most the sum of \(m_{t,\theta}2^\theta\mu^{(k)}_t(S)/\binom nt\) over the pairs \((t,\theta)\) with \(t\le|S|\). There are at most \((k+1)(\Theta+1)\) such pairs, and each term is at most \(8\Gamma(\kappa(\Theta+1)+1)2^{\psi n}\max_{t'\le|S|}\mu^{(k)}_{t'}(S)/\binom n{t'}\); this gives the bound on the expectation. By Markov’s inequality, the probability that some trial runs \(\mathcal{A}\) on a subset of \(S\) is at most this expectation, which gives the bound \(1/4\). ∎
The moments with a larger size bound are easy to bound for the running-time exponents of this paper, which grow with the size bound. If \(g(I,X,k)\) is nondecreasing in \(k\), then for every \(S\in\mathcal{F}_I\), every \(k\ge|S|\) and every \(t\le|S|\), each term of (3) satisfies \(2^{-g(I,X,k)}\le2^{-g(I,X,|S|)}\); hence \[\tag{4} \mu^{(k)}_t(S)\le\mu^{(|S|)}_t(S)=\mu_t(S),\] where \(\mu_t(S)\) is the exponential moment of Definition 3.3 for \(S\) and its own size \(|S|\). For such running-time exponents, Proposition 3.10 therefore bounds the runs on \((I,k)\) for all \(k\ge|S|\) by the moments of \(S\) for \(k=|S|\).
3.5 Optimality in its class
Proposition 3.10 concerns one algorithm and one solution. We now show that Algorithm MLS-\(\theta\) is optimal, up to polynomial factors and on every instance, among all algorithms that sample uniformly, run \(\mathcal{A}\) only on samples whose running-time exponent is at most a chosen threshold \(\theta\), and are charged \(2^\theta\) per trial (the class \(\mathcal{C}_{\mathrm{thr}}\) defined below). Consequently a running time below the one certified by Theorem 3.5, by more than a polynomial factor, needs trials outside this class (Appendix A); a sharper analysis of Algorithm MLS-\(\theta\) cannot give it.
Fix \(I\), \(k\le n\) and a correct extension algorithm \(\mathcal{A}\) with running-time exponent \(g\), and write \(U=U_I\) and, as declared after Definition 3.2, \(g(X)=g(I,X,k)\).
Definition 3.11 (Extendable sets and the class optimum). The family \(\mathcal{E}\) of extendable sets consists of the sets \(X\subseteq U\) with \(|X|\le k\) such that \(X\cup Y\in\mathcal{F}_I\) for some \(Y\subseteq U\setminus X\) with \(|Y|\le k-|X|\); put \(\mathcal{E}_t=\mathcal{E}\cap\binom Ut\). Since \(\mathcal{A}\) is correct, it accepts \((I,X,k)\) exactly when \(X\in\mathcal{E}\), and \(\binom St\subseteq\mathcal{E}_t\) for every \(S\in\mathcal{F}_I\) with \(|S|=k\). For an integer \(\theta\ge0\) let \(q_\theta(t)\) be the number of \(X\in\mathcal{E}_t\) with \(g(X)\le\theta\), let \(\mu_t(\mathcal{E})=\sum_{X\in\mathcal{E}_t}2^{-g(X)}\), and define the class optimum \[\pi^*=\max_{0\le t\le k,\ \theta\in\mathbb Z_{\ge0}}\frac{q_\theta(t)\,2^{-\theta}}{\binom nt}.\]
The maximum exists, because for each \(t\) the count \(q_\theta(t)\) is constant for \(\theta\ge\max g\), so only finitely many values of \(\theta\) are candidates. Note that \(\mu_t(\mathcal{E})\ge\mu_t(S)\) for every \(S\in\mathcal{F}_I\) with \(|S|=k\).
Let \(\mathcal{C}_{\mathrm{thr}}\) be the class of algorithms that perform a sequence of trials of the following kind. Before trial \(i\) the algorithm chooses \(t_i\in\{0,\dots,k\}\) and an integer \(\theta_i\ge0\), as any, possibly randomized, function of everything observed so far; negative thresholds would pass nothing, as \(g\ge0\). Trial \(i\) draws \(X_i\) uniformly from \(\binom U{t_i}\), independently of the past. If \(g(X_i)\le\theta_i\) it runs \(\mathcal{A}\) on \((I,X_i,k)\), and it answers yes if \(\mathcal{A}\) accepts; these are the only yes answers of the algorithm. Trial \(i\) is charged \(2^{\theta_i}\), whether or not \(\mathcal{A}\) is run. Algorithm MLS-\(\theta\) belongs to \(\mathcal{C}_{\mathrm{thr}}\), and its running time is its total charge times \(N^{O(1)}\). Under this charge the threshold filter is the filter with the largest success probability: a filter must reject every \(X\) with \(g(X)>\theta\) to keep the running-time bound of the trial within \(2^\theta N^{O(1)}\), and rejecting more samples only lowers the success probability.
Theorem 3.12 (Optimality in its class). Let \(I\), \(k\), \(\mathcal{A}\) and \(g\) be as fixed above, and \(\mathcal{E}_t\), \(q_\theta(t)\), \(\mu_t(\mathcal{E})\) and \(\pi^*\) as in Definition 3.11. Then:
(a) every algorithm in \(\mathcal{C}_{\mathrm{thr}}\) whose total charge is at most \(\mathsf B\) on every run answers yes with probability at most \(\mathsf B\pi^*\);
(b) if \(\pi^*\ge2^{-\psi n}/\Gamma\), then Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\) answers yes with probability at least \(1-e^{-\kappa}\), and it runs in time \(2^{\psi n}N^{O(1)}\) by Theorem 3.5(i);
(c) for every \(t\) and every integer \(\theta\), \(q_\theta(t)2^{-\theta}\le\mu_t(\mathcal{E})\). If, for an integer \(g_{\max}\ge0\), \(g\) takes integer values in \(\{0,\dots,g_{\max}\}\) on \(\mathcal{E}_t\), then \(\max_{0\le\theta\le g_{\max}}q_\theta(t)2^{-\theta}\ge\mu_t(\mathcal{E})/(g_{\max}+1)\).
The proof is in Appendix D.1. For (a) it bounds the success probability of each trial by \(\pi^*\) times its charge and sums over the trials; for (b) it uses the trials of a pair \((t,\theta)\) that attains \(\pi^*\); and (c) compares each threshold with the running-time exponents below it.
By (a) and (b), Algorithm MLS-\(\theta\) with \(\Gamma=1\) and \(2^{\psi n}=1/\pi^*\) is optimal in \(\mathcal{C}_{\mathrm{thr}}\) up to polynomial factors; in a worst-case analysis, \(2^{\psi n}\) is an upper bound on \(1/\pi^*\) proven for a whole family of instances. By (c), \(1/\pi^*\) equals \(\min_t\binom nt/\mu_t(\mathcal{E})\) up to a factor \(g_{\max}+1\) for integer running-time exponents bounded by \(g_{\max}\). For real-valued \(g\), Lemma 3.8(a) takes the place of the integer case of (c): with \(\xi=g(X)\) if \(X\in\mathcal{E}_t\) and \(\xi=\infty\) otherwise, for \(X\) uniform in \(\binom Ut\), the definitions of \(\mu_t(\mathcal{E})\) and \(q_\theta(t)\) give \(\mathbb{E}[2^{-\xi}]=\mu_t(\mathcal{E})/\binom nt\) and \(\Pr[\xi\le\theta]=q_\theta(t)/\binom nt\). Since Algorithm MLS-\(\theta\) succeeds on every extendable sample, (b) and (c) also show that Theorem 3.5(iii) remains true when \(\mu_t(S)\) in (\(\star\)) is replaced by the sum \(\mu_t(\mathcal{E})\) over the \(t\)-subsets of all solutions of size at most \(k\): for Algorithm MLS-\(\theta\)\((\psi,(g_{\max}+1)\Gamma,\kappa)\) when \(g\) takes integer values in \(\{0,\dots,g_{\max}\}\) on \(\mathcal{E}\) for an integer \(g_{\max}\le N^{O(1)}\), and for Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\) itself, for any \(g\), when the whole left-hand side of (\(\star\)) is replaced by \(\pi^*\).
3.6 General forms
The proof of Theorem 3.5 uses only two properties of a trial: it runs in time at most \(2^\theta N^{O(1)}\), and it succeeds whenever a random quantity attached to it is at most \(\theta\). This subsection isolates that structure in a version for arbitrary budgeted trials, which covers randomized extension algorithms and the closure sampling of Section 8.
The general form rests on Lemma 3.8. The next theorem replaces the trials of Algorithm MLS-\(\theta\) by arbitrary randomized procedures. A trial indexed by \(\iota\) with threshold \(\theta\) must run in time \(2^\theta N^{O(1)}\) and must succeed at least when a random variable \(\xi_{\iota}\), which the analysis attaches to it, is at most \(\theta\). The variable \(\xi_{\iota}\) is only used in the analysis; it may depend on an unknown solution.
Algorithm 3.13 (Budgeted trials). an instance \(I\) and an integer \(k\le n\). a randomized algorithm \(\mathrm{Tr}\) with inputs \((I,k,\iota,\theta)\) and, for each \((I,k)\), a set \(\mathcal{T}=\mathcal{T}_{I,k}\) of indices; for \(\iota\in\mathcal{T}\) and an integer \(\theta\ge0\), the run of \(\mathrm{Tr}\) on \((I,k,\iota,\theta)\) is the trial \(\mathrm{Tr}_{\iota,\theta}\). Further \(\psi\), \(\Gamma\) and \(\kappa\), with a cap \(\Theta\) and trial counts \(m_{\iota,\theta}\) as in (2) with \(\iota\) in place of \(t\). For every \(\iota\in\mathcal{T}\) and \(\theta\in\{0,\dots,\Theta\}\), run \(m_{\iota,\theta}\) independent trials \(\mathrm{Tr}_{\iota,\theta}\), and answer yes as soon as one accepts. Answer no after all trials.
Theorem 3.14 (Budgeted trials). Let \(\Phi\) be an implicit set system, and let \(\mathrm{Tr}\) and the index sets \(\mathcal{T}=\mathcal{T}_{I,k}\) be as in Algorithm 3.13, such that \(\mathcal{T}_{I,k}\) can be listed in time \(N^{O(1)}\). Suppose that there is a polynomial \(p\) such that for every instance \(I\), every integer \(k\le n\), every \(\iota\in\mathcal{T}_{I,k}\) and every integer \(\theta\ge0\)
(T1) \(\mathrm{Tr}_{\iota,\theta}\) runs in time \(2^\theta p(N)\) and in space \(p(N)\) plus \(\mathrm{sp}\), where \(\mathrm{sp}\ge0\) depends only on \(I\) (for example, the space of an extension algorithm on \(I\)), and
(T2) \(\mathrm{Tr}_{\iota,\theta}\) rejects if \(\mathcal{F}_I\) contains no set of size at most \(k\).
Fix \(I\) and \(k\), let \(S\in\mathcal{F}_I\) with \(|S|=k\), and suppose that for each \(\iota\in\mathcal{T}\) there is a random variable \(\xi_{\iota}\) with values in \([0,\infty]\), whose distribution may depend on \(S\) but not on \(\theta\), such that
(T3) \(\Pr[\mathrm{Tr}_{\iota,\theta}\text{ accepts}]\ge\Pr[\xi_{\iota}\le\theta]\) for every integer \(\theta\ge0\).
Let \(\psi\), \(\Gamma\), \(\kappa\) be as in Theorem 3.5. Then Algorithm 3.13, run with these trials and parameters, runs in time \(2^{\psi n}N^{O(1)}\) and space \(N^{O(1)}+\mathrm{sp}\), 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 \[\max_{\iota\in\mathcal{T}}\mathbb{E}[2^{-\xi_{\iota}}]\ \ge\ \frac{2^{-\psi n}}\Gamma .\]
Lean, partial: budgeted_sound, budgeted_success, budgeted_success_of_admissible (formalisation)
Proof. Time, space and soundness follow from (T1) and (T2) exactly as items (i) and (ii) of Theorem 3.5; the number of pairs is now \(|\mathcal{T}|(\Theta+1)\le N^{O(1)}\), as \(\mathcal{T}\) is listed in time \(N^{O(1)}\). Fix \(\iota\) with \(\mathbb{E}[2^{-\xi_{\iota}}]\ge2^{-\psi n}/\Gamma\). Then \(2^{-\Theta}\le2^{-\psi n}/(2\Gamma)\le\mathbb{E}[2^{-\xi_{\iota}}]/2\), so Lemma 3.8(a) gives \(\theta\le\Theta\) with \(\Pr[\xi_{\iota}\le\theta]\ge2^\theta\mathbb{E}[2^{-\xi_{\iota}}]/(4(\Theta+1))\ge2^{\theta-\psi n}/(4\Gamma(\Theta+1))\). By (T3) each trial of \((\iota,\theta)\) accepts with probability \(\pi_{\iota,\theta}\ge\Pr[\xi_{\iota}\le\theta]\), the trial count satisfies \(m_{\iota,\theta}\ge M_{\iota,\theta}\ge\kappa/\pi_{\iota,\theta}\), and by independence all these trials fail with probability at most \((1-\pi_{\iota,\theta})^{m_{\iota,\theta}}\le e^{-\kappa}\). ∎
In each application, (T1) and (T2) follow directly from the description of the trial, and only (T3) needs an argument. Theorem 3.5 is the instance \(\mathcal{T}=\{0,\dots,k\}\), in which a trial of \((t,\theta)\) is steps 1–2 of Algorithm MLS-\(\theta\), and \(\xi_t=g(I,X,k)\) if \(X\subseteq S\) and \(\xi_t=\infty\) otherwise; (T3) holds because \(\mathcal{A}\) accepts when \(X\subseteq S\), and \(\mathbb{E}[2^{-\xi_t}]=\mu_t(S)/\binom nt\). The closure algorithm RSC of Section 8 is another instance: its trials add a random closure to a uniform sample before the Steiner computation, so the uniform-sample form of Theorem 3.5 does not apply literally, but Theorem 3.14 does. The next instance allows extension algorithms with one-sided error, as used for Connected Feedback Vertex Set in Section 11.3.
Corollary 3.15 (One-sided-error extension algorithms). Let \(\mathcal{A}\) be a randomized algorithm for \(\Phi\)-Extension that never accepts a no-instance, accepts every yes-instance with probability at least \(1/2\) using its own independent coins, and runs in time \(2^{g(I,X,k)}N^{O(1)}\) for every input and every outcome of its coins, where \(g\) is polynomial-time computable. Then Theorem 3.5 holds for \(\mathcal{A}\) with \(\Gamma\) replaced by \(2\Gamma\) in the cap \(\Theta\) and in the trial counts \(m_{t,\theta}\).
Proof. Apply Theorem 3.14 with \(\mathcal{T}=\{0,\dots,k\}\) and the trials of Algorithm MLS-\(\theta\), now with the randomized \(\mathcal{A}\). Property (T1) holds because the time bound holds for every outcome of the coins, and (T2) because \(\mathcal{A}\) never accepts a no-instance. Let \(\xi_t\) be as above, and let \(\xi'_t\) equal \(\xi_t\) if an independent fair coin shows heads and \(\infty\) otherwise. If \(X\subseteq S\) and \(g(I,X,k)\le\theta\), then \(\mathcal{A}\) is run on a yes-instance and accepts with probability at least \(1/2\), independently of \(X\). Hence \[\Pr[\mathrm{Tr}_{t,\theta}\text{ accepts}]\ge\tfrac12\Pr[\xi_t\le\theta]=\Pr[\xi'_t\le\theta], \qquad \mathbb{E}[2^{-\xi'_t}]=\tfrac12\mathbb{E}[2^{-\xi_t}]=\frac{\mu_t(S)}{2\binom nt}.\] If \(S\) satisfies (\(\star\)) with \(\Gamma\), then \(\max_t\mathbb{E}[2^{-\xi'_t}]\ge2^{-\psi n}/(2\Gamma)\), and Theorem 3.14 with \(2\Gamma\) in place of \(\Gamma\) gives the claim. ∎
Other levers.
Changes of the trials outside the class \(\mathcal{C}_{\mathrm{thr}}\) of Theorem 3.12 are examined in Appendix A. Theorem 3.14 covers every sampling distribution that can be sampled in polynomial time (Theorem A.2); non-uniform sampling can lower the running time by an exponential factor (Proposition A.5), whereas sampling in several adaptive stages cannot (Proposition A.6).