Appendix A Other levers

This appendix extends Theorem 3.5 to every samplable distribution and examines two changes of the class of Theorem 3.12, whose proof is in Appendix D.1. Sampling from a non-uniform distribution can lower the running time by an exponential factor (Proposition A.5), whereas sampling in several adaptive stages cannot (Proposition A.6). Neither has yet given a proven improvement of the running-time bound for Connected Dominating Set, and no result of the main text depends on this appendix. We keep the notation of Section 3, in particular the extendable sets $\mathcal{E}$, the counts $q_\theta(t)$ and the class optimum $\pi^*$ of Definition 3.11.

A.1 Samplable distributions

Uniform $t$-sets are one choice of sampling distribution. The theorem extends to every distribution that can be sampled in polynomial time; the success criterion is then the exponential moment of the distribution over the extendable sets of Definition 3.11. For a distribution $\mathcal X$ on subsets of $U=U_I$ define \[M_{\mathcal X}=\sum_{X\in\mathcal{E}}\mathcal X(X)\,2^{-g(X)} .\]

Algorithm A.1 (MLS-$\theta$ for a distribution $\mathcal X$). an instance $I$ of $\Phi$ and an integer $k\le n$. $\psi$, $\Gamma$, $\kappa$ and a distribution $\mathcal X=\mathcal X_{I,k}$ on subsets of $U_I$. Take a cap $\Theta$ and trial counts $m_\theta$ as in (2) (with a single index in place of $t$). For every integer $\theta\in\{0,\dots,\Theta\}$, repeat $m_\theta$ times: draw $X\sim \mathcal X$; if $|X|\le k$ and $g(X)\le\theta$, run $\mathcal{A}$ on $(I,X,k)$, and answer yes if it accepts. Answer no after all trials.

Theorem A.2 (Exponential-moment Monotone Local Search for samplable distributions). Let $\mathcal{A}$ solve $\Phi$-Extension with running-time exponent $g$, and let $\mathcal X=\mathcal X_{I,k}$ be a distribution on subsets of $U_I$ that can be sampled exactly in time $N^{O(1)}$. Let $\psi,\Gamma,\kappa$ be as in Theorem 3.5. Then Algorithm A.1 is a randomized algorithm that runs in time $2^{\psi n}N^{O(1)}$ and in space $N^{O(1)}$ plus the space of $\mathcal{A}$ and of the sampler, 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 \[M_{\mathcal X}\ \ge\ \frac{2^{-\psi n}}\Gamma ,\] in particular if $\sum_{X\subseteq S}\mathcal X(X)2^{-g(X)}\ge2^{-\psi n}/\Gamma$ for some $S\in\mathcal{F}_I$ with $|S|=k$.

Proof. This is Theorem 3.14 with $\mathcal{T}$ a single index, the trial of Algorithm A.1 as $\mathrm{Tr}_\theta$, and $\xi=g(X)$ if $X\in\mathcal{E}$ and $\xi=\infty$ otherwise, for $X\sim\mathcal X$: a trial takes time $N^{O(1)}$ plus at most $2^\theta N^{O(1)}$ ((T1)), an acceptance of $\mathcal{A}$ certifies a solution of size at most $k$ ((T2)), and on the event $\xi\le\theta$ we have $X\in\mathcal{E}$, hence $|X|\le k$ and acceptance by $\mathcal{A}$ ((T3)). Finally $\mathbb{E}[2^{-\xi}]=M_{\mathcal X}$, and the sufficient condition holds because every $X\subseteq S$ lies in $\mathcal{E}$. ∎

The proof uses only that $\mathcal{A}$ accepts on $\mathcal{E}$. The same statement therefore holds in event form, with $\mathcal{E}$ replaced by any set of samples on which a possibly different extension algorithm is guaranteed to accept, provided that every acceptance certifies the desired output. If $\mathcal X$ is uniform on $\binom Ut$, then $M_{\mathcal X}=\mu_t(\mathcal{E})/\binom nt\ge\mu_t(S)/\binom nt$, which gives item (iii) of Theorem 3.5 for the algorithm that runs Algorithm A.1 once for each $t\le k$: the run for a value of $t$ that attains the maximum in ($\star$) alone succeeds with probability at least $1-e^{-\kappa}$, and the $k+1$ runs multiply the running time by $k+1\le n+1$. If every element is included independently with probability $y/(1+y)$, for a rational $y\ge0$, then $\mathcal X(X)=y^{|X|}/(1+y)^n$ and $M_{\mathcal X}\ge W_S(y)/(1+y)^n$, which gives the generating-function condition of Theorem 3.5 directly. The Bernoulli closure of Algorithm RSC (Section 8) is an instance whose distribution is not a product distribution.

A.2 A bound on the success probability

The lower bounds below compare algorithms by their total charge, a running-time bound that is fixed for each trial. The following bound is the counterpart of Theorem 3.12(a) for arbitrary trials.

Lemma A.3 (Charge bound). Let $\pi\ge0$. Consider an algorithm that performs trials one after another and answers yes at the first success, where trial $i$ is any randomized procedure, chosen as a possibly randomized function of the past, that succeeds or fails and is charged an amount $\mathrm{chg}_i\ge1$ determined by its outcome. Suppose that, conditioned on the history before trial $i$ (including the choice of the trial), trial $i$ succeeds with probability at most $\pi\,\mathbb{E}[\mathrm{chg}_i\mid\text{history}]$, and that the total charge never exceeds $\mathsf B'$. Then the algorithm answers yes with probability at most $\pi\mathsf B'$.

Proof. Let $\mathcal G_{i-1}$ be the history before trial $i$ together with the choice of trial $i$, let $s_i=\Pr[\text{trial $i$ succeeds}\mid\mathcal G_{i-1}]$ and $c_i=\mathbb{E}[\mathrm{chg}_i\mid\mathcal G_{i-1}]$, and let $i_{\max}$ be the number of trials. Every charge is at least $1$, so $i_{\max}\le \mathsf B'$, and $\{i\le i_{\max}\}$ is determined by $\mathcal G_{i-1}$. By hypothesis $s_i\le\pi c_i$, so the union bound gives \[\Pr[{\small\text{YES}}]\le\mathbb{E}\Bigl[\sum_{i\le i_{\max}}s_i\Bigr]\le\pi\,\mathbb{E}\Bigl[\sum_{i\le i_{\max}}c_i\Bigr] =\pi\,\mathbb{E}\Bigl[\sum_{i\le i_{\max}}\mathrm{chg}_i\Bigr]\le\pi\mathsf B' ,\] where the equality holds term by term, since $\mathbb{E}[\mathbf 1[i\le i_{\max}]\mathrm{chg}_i]=\mathbb{E}[\mathbf 1[i\le i_{\max}]c_i]$ by the tower property. ∎

A.3 Non-uniform sampling

Sampling from a non-uniform distribution can lower the running time when the instance exposes classes of elements on which including an element in the sample has different effects on the probability that the sample lies in a solution and on the running-time exponent. A synthetic family below shows that this can change the worst-case exponent; its analysis uses product distributions.

For a product distribution $\pi_p(X)=\prod_{u\in X}p_u\prod_{u\notin X}(1-p_u)$ with rational $p_u$ computed from the instance, the condition of Theorem A.2 becomes $W^p_S:=\sum_{X\subseteq S}\pi_p(X)2^{-g(X)}\ge2^{-\psi n}/\Gamma$ for some $S\in\mathcal{F}_I$ with $|S|=k$. For running-time exponents that are sums of per-element terms on subsets of $S$, namely $g(X)=\gamma+\sum_{u\in S\setminus X}a_u+\sum_{u\in X}b_u$ for $X\subseteq S$, this sum factorizes. Writing $\pi_p(X)=\prod_{u\notin S}(1-p_u)\cdot\prod_{u\in S}\pi_u(X)$ with $\pi_u(X)=p_u$ if $u\in X$ and $1-p_u$ otherwise, and expanding the product over $u\in S$ according to whether $u\in X$, gives \[\tag{23} W^p_S=2^{-\gamma}\prod_{u\notin S}(1-p_u)\prod_{u\in S}\bigl((1-p_u)2^{-a_u}+p_u2^{-b_u}\bigr).\] In the following family the classes are given with the instance.

Proposition A.5 (A two-class family). Let $n$ be even, and consider the two-class family of Definition A.4. Then:

(a) the product distribution with $p_u=1/3$ on $U_A$ and $p_u=3/7$ on $U_B$ gives, by Theorem A.2, time $O^{*}\bigl((3/2)^{n/2}(7/4)^{n/2}\bigr)=O^{*}\bigl(\sqrt{21/8}^{\,n}\bigr)$, with $\sqrt{21/8}=1.6201\ldots$, on every instance of the family;

(b) on the instance with $S=U_B$, every algorithm that, trial by trial, chooses $t$, $\theta$ and a pair of size bounds, draws $X$ uniformly from $\binom Ut$, runs the extension algorithm when its running-time exponent is at most $\theta$, and is charged $2^\theta$ per trial, needs total charge at least $\sqrt3^{\,n}/(2(n+1))$ for success probability $1/2$; here $\sqrt3=1.7320\ldots$.

Proof. (a) Fix the correct pair of size bounds $(k_A,k_B)$, and write $p_j$ for the probability on class $U_j$, $j\in\{A,B\}$. On subsets of $S$ the running-time exponent is a sum of per-element terms, with $a_u=\log c_j$ for $u\in S\cap U_j$, $b_u=0$ and $\gamma=0$. The factorization (23) gives \[W^p_S=\prod_{j\in\{A,B\}}(1-p_j)^{n/2-k_j}\Bigl(\frac{1-p_j}{c_j}+p_j\Bigr)^{k_j}.\] With $p_j=y_j/(1+y_j)$ this equals $\prod_j(1+y_j)^{-n/2}c_j^{-k_j}(1+y_jc_j)^{k_j}$. At $y_j=(c_j-1)/c_j$, that is $p_A=1/3$ and $p_B=3/7$, we have $1+y_jc_j=c_j$, so $W^p_S=\prod_j(1+y_j)^{-n/2}=\prod_j(2-1/c_j)^{-n/2}=(21/8)^{-n/2}$ for every $(k_A,k_B)$. Since the extendable sets are the subsets of $S$, $M_{\mathcal X}=W^p_S$, and Theorem A.2 with the correct pair of size bounds, $\Gamma=1$ and $2^{\psi n}=(21/8)^{n/2}$ gives the claim.

(b) Here $k_A=0$ and $k_B=n/2$. A sample is accepted under a pair of size bounds $(\ell_A,\ell_B)$ only if it is a subset of $U_B$ and $\ell_B\ge n/2$; bounds above the class sizes are not used, so $\ell_B=n/2$, and the running-time exponent is then at least that of the pair $(0,n/2)$. Let $q_\theta(t)$ and $\pi^*$ be computed for the pair $(0,n/2)$. A trial with $t$, $\theta$ and a pair of size bounds chosen before it succeeds only if its uniform sample $X\in\binom Ut$ is a subset of $S$ and passes the threshold $\theta$ under the pair $(0,n/2)$, so, conditioned on the history, it succeeds with probability at most $q_\theta(t)/\binom nt\le\pi^*2^\theta$, while its charge is $2^\theta\ge1$. By Lemma A.3 with $\pi=\pi^*$, success probability $1/2$ needs total charge at least $1/(2\pi^*)$. By Theorem 3.12(c), $\pi^*\le\max_t\mu_t(\mathcal{E})/\binom nt$, and here $\mathcal{E}_t=\binom St$, so $\mu_t(\mathcal{E})=\mu_t(S)=\binom{n/2}t4^{-(n/2-t)}$ for $0\le t\le n/2$. With $\tau=t/n\in[0,\frac12]$, the entropy estimates (1) give \[\frac{\mu_t(S)}{\binom nt}\le(n+1)\,2^{\frac n2H(2\tau)-nH(\tau)-n+2\tau n}=(n+1)\,2^{-nf_{1/2}(\tau)}, \qquad f_{1/2}(\tau)=H(\tau)-\tfrac12H(2\tau)+1-2\tau,\] where $f_{1/2}$ is the function $f_\sigma$ of (9) with $(\beta,\rho,\sigma)=(1,2,\frac12)$, the same function as in the proof of Corollary 9.3. By Remark 4.4, since $p=2^{-\rho}=\frac14<\sigma$, its minimum over $[0,\frac12]$ is $F^*(\frac12)=1+\frac12\log\frac12+\frac12\log\frac32=\frac12\log3$ by (6). Hence $\max_t\mu_t(S)/\binom nt\le(n+1)\sqrt3^{\,-n}$, and the charge is at least $\sqrt3^{\,n}/(2(n+1))$. ∎

The family is synthetic: a sensible algorithm would solve the two parts separately, in time bounded by the larger of the two running times rather than by their product. Its purpose is to show that, for a fixed extension algorithm, the sampling distribution can change the worst-case exponent of Monotone Local Search. For Connected Dominating Set, where degrees are visible, it is open whether importance sampling helps.

A.4 Multi-stage sampling

A uniform multi-stage process starts with $D=\emptyset$ and repeatedly either stops, outputting $D$, or chooses a size $\ell\ge1$ and adds a uniform $\ell$-subset of $U\setminus D$. Its choices may depend on everything seen so far, including earlier draws, running-time exponents of intermediate sets, its own coins and even an oracle for $\mathcal{E}$; it may also abort without output. The next proposition shows that no such process outputs a given set more often than a uniform draw of the same size does, so multi-stage trials are neutral.

Proposition A.6 (Multi-stage sampling). For every uniform multi-stage process and every $Y\subseteq U$, $\Pr[\text{output}=Y]\le1/\binom n{|Y|}$. Consequently, suppose each multi-stage trial is charged $2^\theta$ for a threshold $\theta$ fixed before its first stage, and runs $\mathcal{A}$ on its output $Y$ when $|Y|\le k$ and $g(Y)\le\theta$. Then the trial succeeds with probability at most $\sum_{t\le k}q_\theta(t)/\binom nt\le(k+1)2^\theta\pi^*$, and Theorem 3.12(a) holds for algorithms using such trials with $\mathsf B\pi^*$ replaced by $(k+1)\mathsf B\pi^*$.

Proof. We prove by induction on $|U\setminus D|$ that, from any point of the process at which the current set is $D\subseteq Y$, the probability of eventually outputting $Y$ is at most $1/\binom{n-|D|}{|Y\setminus D|}$, whatever the history and the later choices. If the process stops, it outputs $Y$ only if $D=Y$, with probability at most $1=1/\binom{n-|D|}0$. Suppose it adds a uniform $\ell$-subset $E$ of $U\setminus D$, and put $n'=n-|D|$ and $j=|Y\setminus D|$. It can output $Y$ only if $E\subseteq Y\setminus D$, which is impossible if $j<\ell$. Otherwise, by the induction hypothesis applied at $D\cup E$, the probability is at most \[\sum_{E\in\binom{Y\setminus D}\ell}\frac1{\binom{n'}\ell}\cdot\frac1{\binom{n'-\ell}{j-\ell}} =\frac{\binom j\ell}{\binom{n'}\ell\binom{n'-\ell}{j-\ell}}=\frac1{\binom{n'}j},\] using $\binom{n'}\ell\binom{n'-\ell}{j-\ell}=\binom{n'}j\binom j\ell$. A randomized choice of the action mixes these bounds, which are all at most $1/\binom{n'}j$, and aborting only lowers the probability. The process terminates, because $|D|$ grows at every step that does not stop. Taking $D=\emptyset$ gives the first claim. For the consequence, sum the pointwise bound over the extendable passing sets $Y$, layer by layer, and use $q_\theta(t)/\binom nt\le2^\theta\pi^*$ and $t\le k$. The pointwise bound holds whatever the history, so conditioned on the history before a multi-stage trial with threshold $\theta$ the trial succeeds with probability at most $(k+1)\pi^*2^\theta$, while its charge is $2^\theta\ge1$; Lemma A.3 with $\pi=(k+1)\pi^*$ gives the last claim. ∎

Neutrality needs the charge of a trial to be fixed before the trial starts. If the threshold may be chosen after an early stage, the early stages act as a filter that is not charged $2^\theta$, which we do not analyze further.