1 Introduction
Many exact exponential-time algorithms (Fomin and Kratsch 2010) solve a subset problem: given an instance whose solutions are subsets of a universe of \(n\) elements, find a solution of a given size \(k\). We write \(O^{*}(f(n))\) for \(f(n)\) times a factor polynomial in the input length. When the decimal base of our running times is rounded up from a strictly smaller constant, the big-\(O\) notation absorbs the polynomial factor, so we write \(O(1.7204^n)\) rather than \(O^{*}(1.7204^n)\).
A standard way to solve a subset problem faster than \(2^n\) combines a parameterized algorithm with enumeration. Suppose that solutions of size \(k\) can be found in time \(O^{*}(c^k)\) with \(c<4\). For each \(k\), run this algorithm or enumerate all \(\binom nk\) candidate sets, whichever is faster; the running time is \(O^{*}\left(\max_k\min\left(c^k,\binom nk\right)\right)\). At \(k=n/2\) the two terms are \(c^{n/2}\) and about \(2^n\), and if \(c<4\) then for every fraction \(k/n\) one of the two terms is exponentially smaller than \(2^n\).
Monotone Local Search (Fomin et al. 2019) beats \(2^n\) whenever the extension version of the subset problem is solved in time \(O^{*}(c^{k-t})\), for any constant \(c\). In the extension version, a size-\(t\) part of the solution is given and the question is whether the part can be completed to a full solution of size \(k\). Monotone Local Search draws a random set \(X\) of \(t\) elements, hopes that it lies inside an unknown solution \(S\), and asks an extension algorithm whether \(X\) can be completed by at most \(k-t\) further elements. If the extension algorithm runs in time \(O^{*}(c^{k-t})\), the resulting algorithm runs in time \(O^{*}((2-1/c)^n)\). Gaspers and Lee (Gaspers and Lee 2017) allowed a further factor \(b^{n-t}\) in the running time of the extension algorithm, giving running time \(O^{*}((b+1-1/c)^n)\). We show that an extension algorithm with running time \(O^{*}(b^{n-t}c^{k-t}d^{t})\), for constants \(b,c,d\ge1\) with \(d\le bc\), gives the multivariate bound \(O^{*}((b+d-d/c)^n)\) (Corollary 4.6). In all these versions the running-time bound of the extension algorithm depends only on \(n\), \(t\) and \(k\): every sample of a given size is charged the same, worst-case, running time.
As long as the extension algorithm is used only through such a worst-case running time, the bound \((2-1/c)^n\) cannot be improved, and by a remark in (Esmer et al. 2024) neither can \((b+1-1/c)^n\). (Esmer et al. 2024) consider algorithms whose only problem-specific access is a polynomial-time feasibility test and an extension algorithm with running time \(O^{*}(c^{k-|X|})\), and they show that every randomized algorithm of this kind takes time at least \((2-1/c)^n\) divided by a polynomial in \(n\); their concluding section remarks that the same technique shows the bound of Gaspers and Lee to be optimal. To go below these bounds, an algorithm must therefore use more information about the extension algorithm than its worst-case running time (Section 1.3).
This paper lets the running time of the extension algorithm depend on the sample. Our main theorem (Theorem 3.5) applies to every extension algorithm that, given \((I,X,k)\), decides whether some set of at most \(k-|X|\) further elements completes \(X\) to a solution, in time \(O^{*}(2^{g(I,X,k)})\), for some running-time exponent \(g\) that is computable in polynomial time before the extension algorithm is called (Definition 3.2). For a solution \(S\) of size \(k\) and a sample size \(t\), the exponential moment of \(S\) is \[\mu_t(S)=\sum_{X\in\binom{S}{t}}2^{-g(I,X,k)} .\] The theorem requires one solution \(S\) whose exponential moment, for some \(t\), is large compared with the number \(\binom nt\) of possible samples.
Theorem 1.1 (informal version of Theorem 3.5). Suppose that the extension algorithm runs in time \(O^{*}(2^{g(I,X,k)})\) for a running-time exponent \(g\) that is computable in polynomial time, and let \(\psi\ge0\) be a rational constant. There is a randomized algorithm that, given \(I\) and \(k\), runs in time \(O^{*}(2^{\psi n})\), and in polynomial space if the extension algorithm uses polynomial space; it rejects if \(I\) has no solution of size at most \(k\), and it accepts with probability at least \(1/2\) if some solution \(S\) of size \(k\) satisfies \(\mu_t(S)\ge\binom nt2^{-\psi n}\) for some \(t\).
Theorem 1.1 follows from Theorem 3.5 with \(\Gamma=\kappa=1\). The algorithm is simple: it tries every sample size and every integer threshold \(\theta\), and for each pair it draws about \(2^{\psi n-\theta}\) samples and calls the extension algorithm only on those with \(g(I,X,k)\le\theta\). It never needs to know which sample size or threshold is the right one. For one sample size, the probabilistic core of the theorem is the counterpart of Scaman’s analysis of restart strategies (Scaman 2023), and the mean-exponent form (Theorem 4.1) is the counterpart of Zamir’s Markov cutoff (Zamir 2023) (Appendix B).
What is new compared with restarts and cutoffs.
One might summarize the algorithm as “run the extension algorithm only on samples whose running time is below a threshold, and optimize the restart schedule”. Five features separate our setting from restart and cutoff strategies for Las Vegas algorithms, and the analyses in this paper use all five.
(i) The running-time exponent \(g(I,X,k)\) is computed in polynomial time before the extension algorithm is called, so a sample above the threshold is skipped at polynomial cost instead of being run and cut off.
(ii) A call can succeed only if \(X\subseteq S\) for an unknown solution \(S\), so the moment \(\mu_t(S)\) sums \(2^{-g(I,X,k)}\) over the subsets of \(S\) only; a sample outside every solution plays the role of a run that never succeeds. The algorithm thus balances the number of samples inside \(S\) with a small running-time exponent against the running times of their extension calls.
(iii) The running-time exponent depends on the structure of the sample \(X\), not only on its size.
(iv) The generating function \(W_S\) defined below collects the moments of all sample sizes, so no sample size has to be guessed.
(v) \(W_S\) is bounded from below by combinatorial recursions over the structure of the sampled subsets of \(S\), such as dynamic programming along a spanning tree of \(S\); all our applications are analyzed in this way.
Using the exponential moment instead of the mean of \(g\) can gain an exponential factor. If half of the \(t\)-subsets of \(S\) have running-time exponent \(n/4\) and the other half have exponent \(3n/4\), then the worst case charges running time \(2^{3n/4}\) for a sample in \(S\) and the mean charges \(2^{n/2}\), whereas the exponential moment charges at most \(2^{n/4+1}\), so the faster half determines it. Section 2.1 gives the extreme case of exponents \(0\) and \(n\). In general Jensen’s inequality shows that the exponential moment never certifies a larger running time than the mean. Within the class of algorithms that sample uniformly, threshold on \(g\) and are charged \(2^\theta\) for a call at threshold \(\theta\), exponential moments measure, up to polynomial factors, exactly what thresholded sampling can use (Theorem 3.12), and in a black-box model the theorem cannot in general be derandomized without exponential loss (Section 9.2). These optimality statements are limited to the models in which they are proved; they are not lower bounds against other algorithms for the problems themselves. For concrete extension algorithms, we bound exponential moments from below via generating functions along a spanning tree of the solution. Adapting an entropy argument of Csikvári and Lin (Csikvári and Lin 2014) to weighted counts, we show that paths are the worst connected solutions for the tree partition function that bounds these generating functions from below, up to a constant factor.
1.1 Why sample-dependent running times
The motivating example is Max Leaf Spanning Tree (MaxLeaf): given a connected graph \(G\), find a spanning tree with as many leaves as possible. For \(n\ge3\), the maximum number of leaves is \(n-\gamma_{\mathrm{c}}(G)\), where \(\gamma_{\mathrm{c}}(G)\) is the minimum size of a connected dominating set, and optimal solutions of MaxLeaf and of Connected Dominating Set, the problem of finding a connected dominating set of minimum size, translate into each other in polynomial time (Lemma 5.1). So a running-time bound for one of them holds for the other up to a polynomial factor, and we state our results for both. Table 1 lists the previous bounds for the two problems, in polynomial and in exponential space, together with ours; the fastest previously published polynomial-space bound, \(1.8619^n\), dates from 2011, setting aside a claimed \(k\)-leaf algorithm that is deemed incorrect (Section 1.3).
Completing a sampled set \(X\) to a connected dominating set is a Steiner tree problem, as in the algorithm of Abu-Khzam, Mouawad and Liedloff (Abu-Khzam, Mouawad, and Liedloff 2011): the terminals are the vertices that \(X\) does not dominate and the components of \(G[X]\). Inclusion–exclusion over branching walks (Nederlof 2013) solves it in time \(2^{|\mathrm{T}(J_X)|}n^{O(1)}\) and polynomial space through a directed Steiner encoding (Lemmas 5.3 and 5.6), where \(J_X\) is the residual instance left by \(X\) (Section 5.2). Denoting the closed neighborhood of \(X\) by \(N[X]\) and the number of connected components of \(G[X]\) by \(\operatorname{comp}(G[X])\), the number of terminals is \[|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\] by Corollary 5.8. This running time depends on the sample, and a single sampled vertex can be worthless: if its closed neighborhood is already dominated and it touches exactly one component of \(G[X]\), adding it to \(X\) leaves the number of terminals unchanged. Accounting that charges every sample of a given size its worst case therefore credits sampling with nothing. Sampling leaves of the spanning tree instead meets another obstacle: the extension problem of MaxLeaf parameterized by the number \(\ell'\) of additional leaves is W[1]-hard (Theorem C.2), so it has no algorithm with running time \(O^{*}(c^{\ell'})\) for a constant \(c\) unless \(\mathrm{FPT}=\mathrm{W}[1]\), and for running times \(b^{n-|X|}d^{|X|}\) (the product form with \(c=1\)) the main theorem certifies, for the worst solution size, nothing below a single call of the extension algorithm on the empty sample (Appendix C.2).
An average sample, by contrast, is valuable. If \(S\) is a connected dominating set of size \(s=\sigma n\) and \(X\) is a uniform \(t\)-subset of \(S\) with \(t\ge1\), then \[\mathbb{E}\,|\mathrm{T}(J_X)|\le n-1-\frac{t(n-2)}{s}\] by Lemma 5.11: a sampled vertex removes on average about \(1/\sigma\) terminals, which divides the running time of the extension algorithm by about \(2^{1/\sigma}\), while the requirement that it lie in \(S\) lowers the success probability only by a factor of about \(1/\sigma\). As \(2^{1/\sigma}>1/\sigma\), an average sampled vertex pays for itself, and sample-dependent running times turn this average gain into a faster algorithm.
1.2 Our results
We make three contributions. First, sample-dependent Monotone Local Search: the main theorem with exponential moments and its generating-function form (Theorem 3.5 and Lemma 3.9). Second, Algorithm RSC with graded closure sampling, which solves Max Leaf Spanning Tree and Connected Dominating Set in time \(O(1.6991^n)\), together with a deterministic algorithm (Theorem 1.2). Third, the component-count principle: for extension algorithms whose running time doubles with every component of the sample, paths are the worst connected solutions up to a constant factor (Lemma 11.2), which gives our algorithms for Connected Feedback Vertex Set and Connected Vertex Cover (Theorem 1.3). Further consequences of these techniques are collected in Table 2. The companion site (Gaspers 2026) has a reading version of this paper together with the ancillary programs, the certificates and the Lean development.
Monotone Local Search with exponential moments.
Classical Monotone Local Search with sample size \(t\) draws about \(\binom nt/\binom kt\) samples before one of them lies inside \(S\), and it budgets each call of the extension algorithm its worst-case running time \(2^{\gamma}\), so its running time is about \(\binom nt\binom kt^{-1}2^{\gamma}\). In \(\mu_t(S)\), each \(t\)-subset \(X\) of \(S\) contributes \(2^{-g(I,X,k)}\), the reciprocal of the running time of the extension algorithm on \(X\). If \(g\) takes the same value \(\gamma\) on all these subsets, then \(\mu_t(S)=\binom kt2^{-\gamma}\) and the running time \(\binom nt/\mu_t(S)\) of the main theorem is the classical one. In general, let \(\gamma\) be the largest value of \(g\) on these subsets. A subset \(X\) with \(g(I,X,k)=\gamma-j\), whose running-time bound is \(2^j\) times smaller, contributes \(2^j\) times as much to \(\mu_t(S)\) as a subset with \(g(I,X,k)=\gamma\). So the subsets on which the extension algorithm is fast can make \(\mu_t(S)\) exponentially larger than \(\binom kt2^{-\gamma}\), and the running time \(\binom nt/\mu_t(S)\) exponentially smaller than the classical one.
The main theorem (Theorem 3.5) is stated for arbitrary implicit set systems, real-valued running-time exponents, and a polynomial loss factor. Its condition (\(\star\)) asks that \(\mu_t(S)\ge\binom nt2^{-\psi n}\) for some \(t\), up to that factor. To avoid a separate analysis for each \(t\), Lemma 3.9 collects all sample sizes in one polynomial in a variable \(y\), the generating function \(W_S(y)=\sum_t\mu_t(S)\,y^t=\sum_{X\subseteq S}y^{|X|}2^{-g(I,X,k)}\): up to a polynomial factor, the smallest running time \(2^{\psi n}\) for which the theorem applies to a solution \(S\) is \(\inf_{y\ge0}(1+y)^n/W_S(y)\). Our analyses of the applications bound \(W_S(y)\) from below. Exponential moments are the right quantity for this class of algorithms. Condition (\(\star\)) is necessary, up to a polynomial factor, for the algorithm to call the extension algorithm on any subset of \(S\) at all (Proposition 3.10), and no algorithm that draws uniform samples, chooses sample sizes and thresholds \(\theta\) on \(g\), even adaptively, and calls the extension algorithm only on samples with \(g\le\theta\), is faster on any instance by more than a polynomial factor, when each trial is counted with the running time \(2^\theta\) that its threshold allows (Theorem 3.12). The theorem extends to randomized trials, such as samples from any polynomial-time samplable distribution and extension algorithms with one-sided error; it needs only that a trial at threshold \(\theta\) runs in time at most \(2^\theta\) and succeeds whenever a random variable attached to it is at most \(\theta\) (Theorem 3.14, Corollary 3.15 and Theorem A.2).
Corollaries.
If only a bound \(\lambda\) on the mean of \(g\) over the \(t\)-subsets of every solution is known, Jensen’s inequality turns it into a bound on the exponential moment, and the running time is \(O^{*}\left(\binom nt\binom kt^{-1}2^{\lambda}\right)\) (Theorem 4.1). This bound also has a simple, direct proof, by a cutoff at \(\lambda+1\) and Markov’s inequality (Remark 4.2). If the mean decreases by \(\rho\) bits per sampled element, the exponent has a closed form, and sampling pays exactly when \(\rho>\log(1/\sigma)\) at solution fraction \(\sigma=k/n\) (Corollary 4.3). For running times of product form \(b^{n-|X|}c^{k-|X|}d^{|X|}\) the generating function has a closed form, which gives the multivariate bound \(\bigl(b+\min(d,bc)(1-1/c)\bigr)^n\) for all \(b,c,d\ge1\), and hence the theorems of (Fomin et al. 2019) (\(b=d=1\)) and (Gaspers and Lee 2017) (\(d=1\)); conversely, the main theorem certifies nothing better for such running times (Proposition 4.5 and Corollary 4.6). Every gain in this paper therefore comes from the dependence of the running time on the samples.
Applications.
Tables 1 and 2 compare our running-time bounds with the previous ones. The rest of this subsection describes the algorithms and the ideas behind them. All our algorithms use polynomial space, and the randomized ones have one-sided error.
Max Leaf Spanning Tree and Connected Dominating Set.
All four algorithms complete a sample with the Steiner tree algorithm described above, whose running time is exponential in the number of terminals. The randomized ones never output a value below \(\gamma_{\mathrm{c}}(G)\), and they output \(\gamma_{\mathrm{c}}(G)\) with constant probability.
Theorem 1.2 (Theorems 8.1 and 10.4). Max Leaf Spanning Tree and Connected Dominating Set can be solved in polynomial space by a randomized algorithm with one-sided error in time \(O(1.6991^n)\), and by a deterministic algorithm in time \((\sqrt5-\frac12)^n2^{o(n)}=O(1.7361^n)\).
Algorithm RS uses only the mean number of terminals of a sample (Lemma 5.11), through the linear-savings corollary, and runs in time \(O(1.7449^n)\) (Theorem 6.4).
Algorithm RS-\(\theta\) is the same algorithm run with a smaller target running time \(2^{\psi n}\), that is, a smaller rate \(\psi\); the improvement lies in the analysis. Exponential moments are not additive, so the mean bound no longer suffices. Instead we bound the number of terminals by a potential that is local along a spanning tree of the solution, evaluate the generating function of this potential by a three-state recursion, and bound the recursion from below by a convex region that the merge rule maps into itself, following Rote (Rote 2019) and Rosenfeld (Rosenfeld 2021) (Section 2.2). This gives \(O(1.7204^n)\) (Theorem 7.2). On the uniform \((2,2)\)-lobsters, and on graphs whose unique maximum-leaf spanning tree is such a lobster, the algorithm needs time \(\Omega(1.7192^n)\), so the analysis is nearly tight for this algorithm.
Algorithm RSC adds closure sampling: every vertex with at least two sampled neighbors is added to the sample independently, with probability \(0.07\) if it has exactly two and \(0.077\) if it has more. In the tight case of the mean bound the solution induces a star, and its center is the only vertex that can have two or more sampled neighbors. The budgeted form of the main theorem applies to these random trials and gives \(O(1.6991^n)\) (Theorem 8.1).
The deterministic algorithm uses more than the values of the running-time exponent. In a black-box model, every deterministic algorithm is, on some instances, slower than the randomized one by a factor exponential in \(n\), or has cost \(\binom nk\) up to a polynomial factor, even for the mean form of the main theorem (if the mean bound, at least \(1\), is below \(\log\binom kt\) by a linear amount; Section 9 and Appendix D.6). But the number of Steiner terminals is at most an affine function of the sample with nonnegative integer weights, an integer affine certificate. Balanced set-inclusion families, which we list deterministically in polynomial space, derandomize the exponential moments of such certificates (Theorem 9.10). This gives a deterministic polynomial-space algorithm in time \(O(1.7361^n)\) (Theorem 10.4).
| Bound | Type | Space | Year | Source | Method |
|---|---|---|---|---|---|
| \(1.9407^n\) | deterministic | polynomial | 2008 | (Fomin, Grandoni, and Kratsch 2008) | measure and conquer |
| \(1.8966^n\) | deterministic | polynomial | 2011 | (Fernau et al. 2011) | measure and conquer |
| \(1.8962^n\) | deterministic | polynomial | 2014 | (Binkele-Raible and Fernau 2014) | measure and conquer |
| \(1.8619^n\) | deterministic | polynomial | 2011 | (Abu-Khzam, Mouawad, and Liedloff 2011) | branching, Steiner tree |
| \(1.8139^n\) | deterministic | exponential | 2012 | (Binkele-Raible and Fernau 2012) | algorithm for digraphs |
| \(1.7449^n\) | randomized | polynomial | Theorem 6.4 | mean number of terminals | |
| \(\mathbf{1.7361^n}\) | deterministic | polynomial | Theorem 10.4 | affine certificate | |
| \(1.7204^n\) | randomized | polynomial | Theorem 7.2 | exponential moments | |
| \(\mathbf{1.6991^n}\) | randomized | polynomial | Theorem 8.1 | closure sampling |
| Problem | Previous | New | Type | Source |
|---|---|---|---|---|
| Main applications of the component-count principle | ||||
| Connected Feedback Vertex Set | \(1.9526^n\) (Cygan et al. 2022)\(^*\) | \(1.8^n\) | rand. | Thm. 11.8 |
| Connected Vertex Cover | \(1.7088^n\) (Golovach, Heggernes, and Kratsch 2018) | \(1.6444^n\) | rand. | Thm. 11.15 |
| weighted | \(1.7088^n\) (Cygan 2012)\(^*\) | \(1.6444^n\) | rand. | Thm. 11.15 |
| Further consequences | ||||
| Graph Motif | \(1.7088^n\) (Björklund, Kaski, and Kowalik 2016)\(^*\) | \(1.6444^n\) | rand. | Thm. 11.13 |
| Connected \(r\)-Dominating Set, \(r\ge2\) | \(1.8619^n\) (Abu-Khzam, Mouawad, and Liedloff 2011)\(^\dagger\) | \(1.7361^n\) | det. | Thm. 12.2 |
| \(1.7204^n\) | rand. | Thm. 12.2 | ||
| Connected Dominating Set, weighted | \(1.9896^n\) (Abu-Khzam et al. 2025)\(^\dagger\) | \(1.7361^n\) | det. | Thm. 12.3 |
| \(1.7204^n\) | rand. | Thm. 12.3 | ||
| Weakly Connected Dominating Set | \(1.8619^n\) (Abu-Khzam, Mouawad, and Liedloff 2011)\(^\dagger\) | \(1.7361^n\) | det. | Thm. 12.4 |
| Directed Max Leaf Spanning Tree | \(1.9044^n\) (Binkele-Raible and Fernau 2012) | \(1.7361^n\) | det. | Thm. 12.5 |
| Directed Steiner Tree | \(2^{n/2}\) (see §12.5) | \(1.3727^n\) | rand. | Thm. 12.8 |
| Paired Domination | \(1.7159^n\) (Andreev et al. 2024) | \(1.6302^n\) | rand. | Thm. 12.10 |
Connected Feedback Vertex Set.
Our extension algorithm is a Cut & Count algorithm, built on the \(O^{*}(3^k)\) algorithm of (Cygan et al. 2022), that, given a sample \(X\), runs in time \(O^{*}(3^{k-|X|}2^{\operatorname{comp}(G[X])})\): its running time doubles with every component of the sample, so its product form \((b,c,d)=(1,3,2)\) gives nothing. A random subset of a connected solution, however, has far fewer components than vertices once the sample is a sizeable part of the solution. We bound the generating function \(W_S\) from below by a partition function on a spanning tree of \(S\) (Corollary 11.5), and a weighted form of a lower bound of Csikvári and Lin (Csikvári and Lin 2014) on the number of homomorphisms of a tree into a graph shows that, up to a constant factor, this partition function is smallest on paths (Lemma 11.2). The main theorem then gives time \(O^{*}(1.8^n)\) (Theorem 11.8), against the baseline \(O(1.9526^n)\) obtained by balancing \(O^{*}(3^k)\) against enumeration. The analysis is tight for this algorithm: on a family of graphs, every base below \(1.8\) leads to success probability \(o(1)\) (Proposition 11.10).
Other problems with component-count running times.
Let \(c>1\) be a constant, and consider a problem on a graph \(G\) whose solutions induce connected subgraphs of \(G\). For every extension algorithm that runs in time \(O^{*}(c^{k-|X|}2^{\operatorname{comp}(G[X])})\), the Gibbs-type inequality and the main theorem give an algorithm with running time \(O^{*}(((4c-3)/(2c-1))^n)\) (Corollary 11.6). The case \(c=2\), where a sharper analysis gives \(1.6444\) (Lemma 11.12), covers two problems:
Connected Vertex Cover. With Cygan’s weighted \(O^{*}(2^k)\) algorithm (Cygan 2012) as the extension step, we find a minimum-weight connected vertex cover, for polynomially bounded integer weights, in time \(O(1.6444^n)\) (Theorem 11.15).
Graph Motif. Our extension algorithm contracts each component of the sample to one vertex with a new color and then runs the \(O^{*}(2^k)\) algorithm of Björklund, Kaski and Kowalik (Björklund, Kaski, and Kowalik 2016), in time \(O^{*}(2^{k-|X|}2^{\operatorname{comp}(G[X])})\). The exponential moments give \(O(1.6444^n)\) (Theorem 11.13).
For polynomially bounded integer weights, the same analysis gives \(O(1.6444^n)\) for Maximum-Weight Connected \(k\)-Subgraph and \(O^{*}(1.8^n)\) for vertex-weighted Connected Feedback Vertex Set (Theorems 11.16 and 11.17). For the two problems that we consider the main applications of the component-count principle, we obtain the following.
Theorem 1.3 (Theorems 11.8, 11.17 and 11.15). (Weighted) Connected Feedback Vertex Set and (Weighted) Connected Vertex Cover can be solved in polynomial space by randomized algorithms with one-sided error in time \(O^{*}(1.8^n)\) and \(O(1.6444^n)\), respectively, for vertex weights in \(\{1,\dots,w_{\max}\}\) with \(w_{\max}\le n^{O(1)}\).
Further applications.
The analyses of Algorithm RS-\(\theta\) and of the deterministic algorithm use only a spanning tree of the solution and an assignment of each vertex outside the solution to a solution vertex that dominates it, so they extend to Connected \(r\)-Dominating Set and to vertex-weighted Connected Dominating Set and weighted MaxLeaf, with randomized \(O(1.7204^n)\) and deterministic \(O(1.7361^n)\) running times, and to Weakly Connected Dominating Set and Directed Max Leaf Spanning Tree, with a deterministic \(O(1.7361^n)\) running time (Theorems 12.2, 12.3, 12.4 and 12.5); closure sampling does not extend in this way (Remark 12.6). The inclusion–exclusion formula for vertex-weighted directed Steiner trees behind these extensions (Lemma 5.3) is also the extension algorithm for Directed Steiner Tree, which gives randomized \(O(1.3727^n)\) (Theorem 12.8). For Paired Domination, a Tutte-matrix finishing step gives randomized \(O(1.6302^n)\) (Theorem 12.10); both bounds also hold with polynomially bounded integer vertex weights.