2 Overview of the key ideas
This section explains informally why the main theorem has the form it has, and which ideas give the bounds for Connected Dominating Set and for the problems with component-count running times. Every statement in the first four subsections is proved later, at the place cited. Section 2.5 reports recent claims about the Exponential Time Hypothesis together with our assessment of what they imply for the problems of this paper, supported by informal arguments that are not developed into proofs here.
2.1 Why exponential moments
Fix an instance with a solution \(S\) of size \(k\) in a universe of \(n\) elements, and a sample size \(t\). A uniformly random \(t\)-subset \(X\) of the universe lies in \(S\) with probability \(\binom kt/\binom nt\). In classical Monotone Local Search every extension call has the same running time \(O^{*}(c^{k-t})\), so it finds \(S\) in about \(\binom nt/\binom kt\) trials of running time \(O^{*}(c^{k-t})\) each, and optimizing over \(t\) gives the running time \(O^{*}((2-1/c)^n)\). When the running time \(2^{g(X)}\) of an extension call depends on \(X\), where we write \(g(X)\) for the running-time exponent of the sample \(X\) when the target size \(k\) is fixed, the natural first attempt runs the extension algorithm on every sample. Its expected running time per trial is the mean \(\mathbb{E}[2^{g(X)}]\), which the slowest samples dominate.
The algorithm of Theorem 3.5 instead runs the extension algorithm only on samples whose running-time exponent, computed in polynomial time beforehand, is at most a threshold \(\theta\), and discards the other samples. A trial of the pair \((t,\theta)\) then runs in time \(O^{*}(2^\theta)\), and it succeeds with probability \(p_\theta=\Pr[X\subseteq S\text{ and }g(X)\le\theta]\), so this pair finds \(S\) in expected time about \(2^\theta/p_\theta\). The best threshold is characterized by the following two-sided estimate (Lemma 3.8). Write \(\xi=g(X)\) if \(X\subseteq S\) and \(\xi=\infty\) otherwise. Since \(2^{-\theta}\mathbf 1[\xi\le\theta]\le2^{-\xi}\) pointwise, every threshold satisfies \(2^{-\theta}p_\theta\le\mathbb{E}[2^{-\xi}]\). Conversely, splitting \(\mathbb{E}[2^{-\xi}]\) according to the integer part of \(\xi\) shows that one of the thresholds up to about \(\log(1/\mathbb{E}[2^{-\xi}])+1\) attains \(2^{-\theta}p_\theta\ge\mathbb{E}[2^{-\xi}]/\operatorname{poly}(n)\). Moreover, \[\mathbb{E}[2^{-\xi}]=\frac{1}{\binom nt}\sum_{X\in\binom St}2^{-g(X)}=\frac{\mu_t(S)}{\binom nt},\] the normalized exponential moment of the introduction. So the best threshold for sample size \(t\) finds \(S\) in time \(O^{*}\left(\binom nt/\mu_t(S)\right)\). The algorithm knows neither the right \(t\) nor the right \(\theta\), but there are only polynomially many pairs, and it gives each the same running-time budget \(2^{\psi n}\); it succeeds as soon as \(\binom nt/\mu_t(S)=O^{*}(2^{\psi n})\) for some \(t\), which is condition (\(\star\)).
Thresholding can be exponentially better than paying the mean. Suppose that half of the \(t\)-subsets of \(S\) have running-time exponent \(0\) and the other half \(n\). Running the extension algorithm on every sample in \(S\) takes time about \(2^{n-1}\) on average, the mean-exponent theorem (Theorem 4.1) charges \(2^{\mathbb{E}[g]}=2^{n/2}\) per sample, and the exponential moment charges \(1/\mathbb{E}[2^{-g}]\le2\). In general, Jensen’s inequality gives \(\mathbb{E}[2^{-g}]\ge2^{-\mathbb{E}[g]}\), so the exponential moment never certifies a worse running time than the mean, and it certifies a better one whenever the running-time exponent varies.
The same estimate shows that nothing in this class of algorithms does better. Any algorithm that draws uniform samples, picks the sample size and the threshold of each trial, possibly adaptively, and is charged \(2^\theta\) for a trial with threshold \(\theta\), succeeds with probability at most its total charge times \(\max_{t,\theta}2^{-\theta}\Pr[X\text{ extends to a solution and }g(X)\le\theta]\), and by the estimate above this maximum is at most \(\max_t\mu_t/\binom nt\), where \(\mu_t\) sums \(2^{-g(X)}\) over all \(t\)-sets \(X\) that extend to a solution (Theorem 3.12). The exponential moments are therefore not an artifact of the analysis: they measure exactly what thresholded sampling can exploit.
One generating function instead of \(k+1\) moments.
To verify condition (\(\star\)) we use the generating function \(W_S(y)=\sum_{X\subseteq S}y^{|X|}2^{-g(X)}=\sum_t\mu_t(S)y^t\). Comparing it termwise with \((1+y)^n=\sum_t\binom nty^t\) shows that the running time certified for \(S\) is \(\inf_{y\ge0}(1+y)^n/W_S(y)\), up to a factor \(n+1\) (Lemma 3.9). Upper bounds on running times thus become lower bounds on a sum over the subsets of \(S\), for a single well-chosen value of \(y\); this is the form in which all our applications are analyzed. For a product-form running time, \(2^{-g(X)}=b^{-(n-|X|)}c^{-(k-|X|)}d^{-|X|}\), the sum is \(W_S(y)=b^{-n}c^{-k}(1+ybc/d)^k\), and at \(y=(c-1)d/(bc)\) the second factor becomes \(c^k\); this gives \((1+y)^n/W_S(y)=(b+d-d/c)^n\). This is the multivariate bound when \(d\le bc\); for \(d>bc\) the choice \(y=0\) gives at most \((bc)^n\), which is smaller, hence the \(\min(d,bc)\) in Corollary 4.6. This bound subsumes the bounds of (Fomin et al. 2019) (\(b=d=1\)) and of Gaspers and Lee (Gaspers and Lee 2017) (\(d=1\)) (Proposition 4.5 and Corollary 4.6). For such running times the main theorem certifies nothing better, so the gains below come only from the dependence of the running time on the sample.
2.2 Connected Dominating Set: from averages to the shape of the solution
The extension problem and its running time.
Suppose we have a sample \(X\) that is a subset of an unknown minimum connected dominating set \(S\). The extension algorithm must add a set \(Y\) of vertices that dominates the vertices outside \(N[X]\) and such that \(G[X\cup Y]\) is connected: the added vertices must join the components of \(G[X]\) into one connected subgraph. This is a Steiner tree problem with one terminal for each undominated vertex and one for each component of \(G[X]\), which inclusion–exclusion over branching walks (Nederlof 2013) solves in polynomial space and in time \(O^{*}(2^{|\mathrm{T}(J_X)|})\), where \(|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\) is the number of terminals (Lemma 5.6 and Corollary 5.8).
An affine bound and the mean.
Take a spanning tree \(F\) of \(G\) in which all vertices outside \(S\) are leaves, and give each \(u\in S\) the weight \(w(u)=d_F(u)-1\). The weights add up to \(n-2\), and counting the vertices and edges of \(F\) around a nonempty sample gives the pointwise bound \(|\mathrm{T}(J_X)|\le n-1-w(X)\) (Lemma 5.10). Each vertex of \(S\) lies in a uniform \(t\)-subset of \(S\) with probability \(t/|S|\), so on average a sampled vertex removes \((n-2)/|S|\approx1/\sigma\) terminals, where \(\sigma=|S|/n\) (Lemma 5.11). Each further sampled vertex multiplies the probability that the sample lies in \(S\) by about \(\sigma\), so it multiplies the expected number of trials by about \(1/\sigma=2^{\log(1/\sigma)}\); the terminals it removes divide the running time of the extension algorithm by about \(2^{1/\sigma}\). Since \(1/\sigma>\log(1/\sigma)\) for every \(\sigma\in(0,1]\), the second factor wins at every solution size; the linear-savings corollary (Corollary 4.3) turns this into Algorithm RS and time \(O(1.7449^n)\) (Theorem 6.4). The bound on the mean is tight, for instance, when the solution induces a star and every outside vertex has exactly one neighbor in it (Proposition 5.12).
Exponential moments along a tree.
The mean cannot take advantage of the variation of the number of terminals between samples, but the exponential moments reward this variation. To use it, we bound the number of terminals from above by a potential \(\Pi_{F,\nu}(X)\) along a spanning tree \(F\) of \(G[S]\) (Lemma 7.3). Each vertex outside \(S\) is assigned a neighbor in \(S\), its owner, and \(\nu:S\to\mathbb Z_{\ge0}\) is the map that gives, for each solution vertex \(v\), the number \(\nu_v\) of outside vertices that \(v\) owns. The potential adds up three counts: the outside vertices whose owner is not sampled, the solution vertices that are neither sampled nor adjacent in \(F\) to a sampled vertex, and the components of \(F[X]\). The potential is local along \(F\): since \(\operatorname{comp}(F[X])=|X|-e(F[X])\) for the forest \(F[X]\), where \(e(F[X])\) is the number of edges of \(F\) with both ends in \(X\), the potential is a sum over the vertices \(v\in S\) of terms that each depend only on \(\nu_v\) and on which vertices of the closed neighborhood \(N_F[v]\) are sampled. Because of this, its generating function \(\sum_{X\subseteq S}y^{|X|}2^{-\Pi_{F,\nu}(X)}\) can be computed by dynamic programming from the leaves of \(F\) to its root, with a vector of three numbers per vertex and a fixed bilinear rule that merges a child into its parent (Lemma 7.4). What we need is a lower bound on the result that holds for every tree at once. Following the method of Rote (Rote 2019) and Rosenfeld (Rosenfeld 2021) for counting dominating sets in trees, which we turn from upper into lower bounds, we look for a convex region \(\mathcal P\) in \(\mathbb{R}^3\) that is mapped into itself by the merge rule and contains the vector of every single vertex \(v\) up to a factor \(e_1e_2^{\,\nu_v}\), where \(\nu_v\) is the number of outside vertices that \(v\) owns and \(e_1,e_2>0\) are two constants chosen together with \(\mathcal P\): a scale for each solution vertex and a scale for each outside vertex. Then the vector of every tree on the \(s\) solution vertices lies in \(e_1^{\,s}e_2^{\,n-s}\mathcal P\), and a lower bound of order \(e_1^{\,s}e_2^{\,n-s}\) on the generating function follows (Lemma 7.5). The region is the convex hull of finitely many points, enlarged by a cone that the merge rule preserves; for lower bounds this plays the role that a norm plays in the method for upper bounds, and is an antinorm in the sense of Guglielmi and Protasov (Guglielmi and Protasov 2013). Two such regions for the middle solution sizes, with the closed form of RS elsewhere, give Algorithm RS-\(\theta\), which is RS with a smaller rate, and time \(O(1.7204^n)\) (Theorem 7.2). On a family of lobsters it needs time at least \(1.7192^n\), so little remains to be gained for this algorithm (Proposition 7.9).
Changing the samples.
The tight case of the mean bound, a star, suggests a change of the algorithm. A sample of leaves of the star dominates the hub but leaves every sampled leaf in a component of its own; adding the hub would merge these components into one. Algorithm RSC therefore adds every vertex with at least two sampled neighbors to the sample independently, with probability \(0.07\), or \(0.077\) if it has three or more sampled neighbors. The resulting samples are no longer uniform sets of a given size, but the budgeted form of the main theorem (Theorem 3.14) only needs trials that are fast, sound, and accept with probability at least \(\Pr[\xi\le\theta]\) for a random variable \(\xi\) whose distribution does not depend on \(\theta\); then \(\mathbb{E}[2^{-\xi}]\) averages over the random closure. An eight-state version of the tree recursion, which bounds the generating function from below, and a region of the same kind give time \(O(1.6991^n)\) (Theorem 8.1).
Derandomization.
Classical Monotone Local Search is derandomized by replacing random samples with a family of \(t\)-sets that has a member inside every \(k\)-set (Fomin et al. 2019). With sample-dependent running times this is not enough, since the member inside the solution may be one of the slowest samples. In a black-box model, where an algorithm sees the running-time exponent and the extension algorithm only through queries, an adversary can make slow exactly the samples that a deterministic algorithm queries. For target size \(k=n/2\) and the instances that satisfy the mean bounds of Connected Dominating Set, this forces every deterministic algorithm to incur cost at least \(1.7547^n/\operatorname{poly}(n)\), when an extension call on \(X\) takes time \(2^{g(X)}\) and every other query unit time, while the randomized algorithm has cost only \(O^{*}(\sqrt3^{\,n})\) (Corollary 9.3). The affine bound \(|\mathrm{T}(J_X)|\le n-1-w(X)\) above has more structure than the mean: the weights are unknown, but their total is known. A balanced family contains, inside every \(k\)-set and for every nonnegative weighting of it, a sample whose weight is at least the average; such a family plays the role of the random sample in the mean-exponent analysis. We construct balanced families deterministically and in polynomial space (Theorem 9.6). For integer weights, the exponential moments of the affine bound, \(2^{-(n-1)}\prod_{u\in S}\bigl(1+y2^{w(u)}\bigr)\) in generating-function form, can also be achieved deterministically, with two-class balanced families, and this gives a deterministic polynomial-space algorithm in time \(O(1.7361^n)\) (Theorem 10.4).
Other domination variants.
These arguments use the graph only through a spanning tree of the solution and the assignment of every outside vertex to a solution vertex that dominates it. They therefore carry over to distance-\(r\) domination, vertex weights, weakly connected domination and directed graphs, and similar finishing steps give the bounds for Directed Steiner Tree and Paired Domination (Section 12).
2.3 Component-count running times: paths are the worst case
Consider Connected Feedback Vertex Set, Graph Motif and Connected Vertex Cover. When given a sample \(X\) of a connected solution \(S\) of size \(k\), an extension algorithm runs in time \(O^{*}(c^{k-|X|}2^{\operatorname{comp}(G[X])})\), with \(c=2\) or \(c=3\). A sample of size \(t\) can have up to \(t\) components, so the product-form bound is \(c^{k-t}2^t\), which gives nothing better than enumeration. Let \(F\) be a spanning tree of \(G[S]\). Every edge of \(F\) inside \(X\) merges two components, so \(\operatorname{comp}(G[X])\le|X|-e(F[X])\), where \(e(F[X])\) is the number of edges of \(F\) with both endpoints in \(X\), and therefore \[W_S(y)\ \ge\ c^{-k}\sum_{X\subseteq V(F)}\zeta^{|X|}\,2^{e(F[X])}=c^{-k}\mathcal Z_F(\zeta), \qquad\zeta=cy/2,\] a partition function on the tree in which every sampled vertex has weight \(\zeta\) and every edge between two sampled vertices has weight \(2\) (Corollary 11.5). On a path with \(k\) vertices, \(\mathcal Z_F(\zeta)\) is computed by the \(2\times2\) transfer matrix \(M_\zeta=\left( \begin{smallmatrix}1&\zeta\\1&2\zeta \end{smallmatrix}\right)\), whose rows and columns are indexed by the states “not sampled” and “sampled” of a vertex, and it grows like \(\lambda_{\max}(M_\zeta)^k\), where \(\lambda_{\max}(M_\zeta)\) is the largest eigenvalue of \(M_\zeta\). The key lemma (Lemma 11.2) shows that no tree does worse: \(\mathcal Z_F(\zeta)\ge\min(1,\zeta)\lambda_{\max}(M_\zeta)^{k-1}\) for every tree with \(k\) vertices. The proof, a weighted form of an argument of Csikvári and Lin (Csikvári and Lin 2014) for homomorphisms of trees, bounds \(\ln\mathcal Z_F\) from below by the Gibbs variational inequality, using as test distribution the distribution of the labels given by a reversible two-state Markov chain run from the root down the tree, started in its stationary distribution. Then every vertex and every edge has the same label distribution, whatever the shape of the tree, and the bound is the same as for a path. Concretely, the Gibbs inequality bounds \(\ln\mathcal Z_F(\zeta)\) from below by the entropy of the test distribution plus the expected logarithm of the weight \(\zeta^{|X|}2^{e(F[X])}\). For the Markov chain both terms split into a term for the root and one term for each of the \(k-1\) edges, and since every edge has the same joint label distribution, whichever endpoint is the parent, all edge terms are equal. The chain is built from the Perron eigenvector of a symmetric matrix with the same eigenvalues as \(M_\zeta\), and this choice makes each edge term exactly \(\ln\lambda_{\max}(M_\zeta)\). The lemma is a statement about the partition function \(\mathcal Z_F\), which bounds \(W_S\) from below; it does not say that paths are the hardest instances of the problems. With paths identified as the worst case of this lower bound, the choice of \(y\) is a one-dimensional optimization. It gives \(O^{*}(((4c-3)/(2c-1))^n)\) in closed form for every \(c>1\) (Corollary 11.6), which is \(O^{*}(1.8^n)\) for Connected Feedback Vertex Set, and no smaller base works for this algorithm (Proposition 11.10). For \(c=2\), further optimization gives \(O(1.6444^n)\) for Graph Motif and Connected Vertex Cover (Theorems 11.13 and 11.15).
2.4 Computer certificates
The following bounds rest on computations: the bases \(1.7449\), \(1.7204\), \(1.6991\) and \(1.7361\) of RS, RS-\(\theta\), RSC and the deterministic algorithm (Theorems 6.4, 7.2, 8.1 and 10.4), the bases \(1.6444\) for \(c=2\), \(1.3727\) for Directed Steiner Tree and \(1.6302\) for Paired Domination (Theorems 11.13, 12.8 and 12.10), and the lower bound \(1.7192^n\) for RS-\(\theta\) on the uniform lobsters. For RS-\(\theta\) and RSC, the points that span the regions \(\mathcal P\) of Section 2.2 are found by computer: the certificate of RSC has \(1024\) rational points. Each certificate lists its points and is checked by programs that verify the finitely many inclusions in exact rational arithmetic. The two certificates of RS-\(\theta\) are checked by three independent programs and the certificate of RSC by two; the second program for RSC was written from the definitions without reusing code of the first, re-derives the recursion and rejects perturbed copies of the certificate (Appendices F.2 and F.4). Both RS-\(\theta\) certificates, and the reduction of the bound for RSC to the finite conditions of its certificate, are also checked in Lean 4 (Appendix F.9); there the conditions of the RSC certificate are checked as well, by compiled evaluation, which also trusts the Lean compiler. The lobster bound and the three certificates for Directed Steiner Tree are also checked in Lean, by the kernel alone, without compiled evaluation. The rates of these certificates, the constant of Theorem 6.4, the optimization over \(y\) behind the base \(1.6444\) for \(c=2\), and the finitely many cases behind the base \(1.6302\) are checked in exact rational arithmetic, or in ball arithmetic with outward rounding where logarithms, exponentials and square roots occur. Appendix F says which statement rests on which program or certificate. The programs, the certificates and the Lean development are on the companion site (Gaspers 2026), together with a reading version of the paper that links each statement to them. The base \(1.8\) for Connected Feedback Vertex Set has a proof without computation (Corollaries 11.5 and 11.6), and the proof of the base \(\sqrt5-\frac12\) needs one algebraic identity and ten rational inequalities checked in exact arithmetic (Lemma 10.1).
2.5 The Exponential Time Hypothesis
Recent preprints by OpenAI (OpenAI 2026) and Claude (Anthropic) (Claude (Anthropic) 2026) claim to refute the Exponential Time Hypothesis. This would give subexponential time algorithms for 3-SAT and imply subexponential time algorithms for every problem with a SERF reduction to 3-SAT (Impagliazzo, Paturi, and Zane 2001). This includes all problems in SNP and size-constrained SNP; for example, Vertex Cover, Independent Set and \(k\)-Set Cover. We are not aware of SERF reductions to 3-SAT for any of the problems in Tables 1 and 2, nor of subexponential-time algorithms for them under either claim. The obstacle that we see is a global constraint on the solution. All these problems except Paired Domination require the solution to be connected, and so they are not evidently in SNP: universal first-order constraints on a witness are preserved under induced substructures, whereas connectivity is not, since deleting the middle vertex of a path on three vertices disconnects it. Moreover, a natural CNF encoding of connectivity, by parent pointers of a spanning tree, uses \(\Theta(n\log n)\) variables, and with \(\Theta(n\log n)\) variables the claimed bounds do not give subexponential time. For Paired Domination, the subgraph induced by the solution must have a perfect matching, and a natural encoding by a partner pointer for each vertex also uses \(\Theta(n\log n)\) variables.
2.6 Organization
Section 3 sets up implicit set systems, running-time exponents and exponential moments, and proves the main theorem and its general forms. It also shows that the algorithm is optimal in its class. Section 4 derives the mean-exponent theorem, the linear-savings corollary and multivariate Monotone Local Search. The applications are grouped by problem family. Section 5 prepares the applications to Connected Dominating Set and MaxLeaf and states the vertex-weighted directed Steiner lemma that the later sections use; Sections 6, 7 and 8 present Algorithms RS, RS-\(\theta\) and RSC; Section 9 states the black-box barrier and gives the derandomization for affine certificates; and Section 10 gives the deterministic algorithm. Section 11 treats component-count running times: it proves that paths are the worst case, up to a constant factor, of the partition function that bounds the exponential moments from below, and then treats Connected Feedback Vertex Set, Graph Motif, Connected Vertex Cover and their variants, one problem at a time. The section on further applications (Section 12) transfers the algorithms for Connected Dominating Set to connected \(r\)-domination, vertex weights, weak connectivity and directed graphs, and treats Directed Steiner Tree and Paired Domination (Sections 12.5 and 12.6). Section 13 lists open problems. The appendices treat samplable distributions and other levers (Appendix A), related mechanisms outside Monotone Local Search (Appendix B), linear savings, product-form running times and the hardness of MaxLeaf-Extension (Appendix C), and the computer certificates (Appendix F). Appendix D contains the proofs that the main text defers: optimality in its class (Appendix D.1), linear savings and product-form running times (Appendix D.2), the Steiner computations (Appendix D.3), the analysis of RS-\(\theta\) and its lower bound (Appendix D.4), the closure bound of RSC (Appendix D.5), the black-box barrier (Appendix D.6), the balanced families and the count of trees across block partitions (Appendix D.7), the deterministic algorithms (Appendix D.8), the extension algorithm and the tightness results for Connected Feedback Vertex Set (Appendix D.9), the weighted finishing steps (Appendix D.10), and the further applications, among them Directed Steiner Tree and Paired Domination with their vertex-weighted versions (Appendix D.11); Appendix E lists, for every application, the imported results, the randomness, the weights and the output.