13 Conclusion and open problems
Monotone Local Search needs only large exponential moments \(\mu_t(S)\) of the running-time exponent over the subsets of one solution (Definition 3.3 and Theorem 3.5), rather than a worst-case running-time bound for every sample of a given size; the criterion is necessary for Algorithm MLS-\(\theta\) (Proposition 3.10), the algorithm is optimal within the class of Theorem 3.12, and for product-form running-time exponents it certifies the multivariate bound and, up to polynomial factors, nothing better (Corollary 4.6 and Proposition 4.5). The gains come from extension algorithms whose running time depends on the structure of the sample, such as the number of Steiner terminals or of components of the sample. Several questions remain open.
1. Derandomization. The black-box barrier of Section 9 rules out a general derandomization, and balanced set-inclusion families derandomize only the bounds that come from integer affine certificates (Section 10). Can RS-\(\theta\) or RSC be derandomized with a factor \(2^{o(n)}\)? Their analyses rest on tests along an unknown spanning tree of the solution; a counting argument shows that against every family of \(2^{O(n)}\) partitions into blocks of size \(n^{o(1)}\) some such tree has almost all of its edges between blocks, so these tests are not separable over the blocks of a product construction (Proposition D.7.7).
2. Better trials for Connected Dominating Set. Algorithm MLS-\(\theta\) is optimal within the class of Theorem 3.12, so with the same extension algorithm and running-time exponent further gains must come from trials outside this class: a non-uniform sampling distribution (Appendix A), a rule that adds vertices to the sample, as RSC does, or an accounting that charges a trial only for the extension call that it actually makes. For Connected Dominating Set we do not know whether any of these improves on Theorem 8.1.
3. Component-count running times. For \(c=3\) the base \(1.8\) is exact for Algorithm MLS-\(\theta\) (Propositions 11.9 and 11.10), so further progress for Connected Feedback Vertex Set needs a different extension algorithm or a different trial. For \(c=2\) the proved base \(1.6444\) is within \(2\cdot10^{-4}\) of the value \(2^{\psi_2}\approx1.64429\) that Theorem 3.5 certifies for a solution whose spanning tree is a path (Section 11.2), but we have no family of instances of Graph Motif or Connected Vertex Cover on which this value is tight. No deterministic algorithm for Connected Feedback Vertex Set in time \(O((2-\varepsilon)^n)\) is known to us; it would need to derandomize both the sampling and the Cut & Count step. Nor do we know of an analysis that bounds a natural branching extension algorithm (branching on whether a vertex on a cycle joins the solution, followed by a Steiner phase) below \(2^n\).
4. Closure rules elsewhere. Does a closure rule, as in RSC, lower the running time for Directed Steiner Tree, or give \(O(1.6991^n)\) for Connected \(r\)-Dominating Set with \(r\ge2\) (Remark 12.6)?
5. Other problems and enumeration. Our method applies whenever the running time of the extension algorithm is exponential in a polynomial-time computable structural parameter of the sample whose exponential moments over the subsets of a solution are large. It would be interesting to characterize the problems for which Theorem 3.5 is exponentially better than every bound from a product-form running-time exponent. (Fomin et al. 2019) also turn product-form Monotone Local Search into enumeration algorithms; we have not studied enumeration with sample-dependent running times.