Monotone Local Search with Sample-Dependent Running Times
Version. This reading version renders the manuscript of 1 November 2026 (release v1.1), the same version as the PDF. Section, statement, equation and table numbers match the PDF. The paper is arXiv:2611.01774 and has not been published in a journal or conference proceedings; its evidence release v1.1 is archived on Zenodo. A short version (PDF only, 28 pages, with its own numbering) states the main results and proves the main theorem; it refers to this full version for the remaining proofs.
Abstract
Monotone Local Search turns an algorithm that extends a given partial solution into an algorithm that finds a solution from scratch: sample a few elements, hope that they lie in an unknown solution, and complete them. Its known analyses bound every call of the extension algorithm by a worst-case time that depends only on the number of sampled elements, and Esmer, Kulik, Marx, Neuen and Sharma (SODA 2024) showed that no algorithm that uses the extension algorithm only as a black box with this worst-case running time beats the original form by more than a polynomial factor. We let the running time of the extension algorithm depend on the actual sample. If it decides in time \(O^{*}(2^{g(I,X,k)})\), for a polynomial-time computable \(g\), whether a sample \(X\) can be completed to a solution with at most \(k\) elements, our main theorem gives a randomized algorithm with one-sided error in time \(O^{*}(2^{\psi n})\) that accepts with probability at least \(1/2\) whenever, for some solution \(S\) of size \(k\) in a universe of \(n\) elements and some \(t\), the exponential moment \(\sum_{X\subseteq S,|X|=t}2^{-g(I,X,k)}\) is at least \(2^{-\psi n}\binom nt\). A corollary, multivariate Monotone Local Search, generalizes the theorems of Fomin, Gaspers, Lokshtanov and Saurabh (STOC 2016 & J. ACM 2019) and of Gaspers and Lee (ICALP 2017).
For Max Leaf Spanning Tree and, equivalently, Connected Dominating Set, the previous fastest known algorithms run in time \(O^{*}(1.8619^n)\) in polynomial space and \(O^{*}(1.8139^n)\) in exponential space. Completing a sample is a Steiner tree problem, solved in time exponential in the number of terminals, which varies strongly with the sample. We obtain a randomized polynomial-space algorithm with one-sided error in time \(O(1.6991^n)\) and a deterministic polynomial-space algorithm in time \((\sqrt5-\frac12)^{n}2^{o(n)}=O(1.7361^n)\). For connectivity problems in which the running time of the extension algorithm doubles with every component of the sample, an analysis through a partition function gives randomized polynomial-space algorithms in time \(O^{*}(1.8^n)\) for Connected Feedback Vertex Set and \(O(1.6444^n)\) for Connected Vertex Cover, both also with vertex weights.
Contents
- 1 Introduction
- 2 Overview of the key ideas
- 3 Monotone Local Search with sample-dependent running times
- 4 Corollaries: mean exponents, linear savings and product form
- 5 Connected Dominating Set and Max Leaf Spanning Tree
- 6 Warm-up: sampling a connected dominating set with the mean running-time exponent
- 7 Exponential moments of the Steiner extension: Algorithm RS-\(\theta\)
- 8 Closure sampling under exponential moments: Algorithm RSC
- 9 Derandomization
- 10 Deterministic algorithms in polynomial space
- 11 Component-count running times
- 12 Further applications
- 13 Conclusion and open problems
- Acknowledgments
- AI methodology
Appendices
How to cite
Serge Gaspers. Monotone Local Search with Sample-Dependent Running Times. arXiv:2611.01774, 2026. doi:10.48550/arXiv.2611.01774.
The evidence release (PDF, LaTeX source, Lean project, certificates and checkers):
Serge Gaspers. Monotone Local Search with Sample-Dependent Running Times: Companion site with ancillary programs, certificates and Lean 4 formalization. Software and data, version v1.1. Zenodo, 2026. doi:10.5281/zenodo.23851002.
Artifacts
The paper relies on computer certificates for several of its bases. Appendix F lists them and the arithmetic they check; the files are in ancillary/, and the formalisation page links each certified or Lean-proved statement to its evidence.