arXiv:2611.01774 · v1
Monotone Local Search with Sample-Dependent Running Times
摘要
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 et al. (SODA 2024) showed that no algorithm that uses the extension algorithm as a black box with this running time beats the original form by more than a polynomial factor. We let this running time depend on the actual sample. If the extension algorithm 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^{ψn})$ whenever, for some solution $S$ of size $k$ and some $t$, the exponential moment $\sum_{X\subseteq S,|X|=t}2^{-g(I,X,k)}$ is at least $2^{-ψn}\binom{n}{t}$. A corollary, multivariate Monotone Local Search, generalizes the theorems of Fomin et al. (STOC 2016, J. ACM 2019) and of Gaspers and Lee (ICALP 2017). For Max Leaf Spanning Tree and, equivalently, Connected Dominating Set, the previous best polynomial-space bound is $O^*(1.8619^n)$. 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 in time $O(1.6991^n)$ and a deterministic one in time $(\sqrt5-\frac12)^n 2^{o(n)}=O(1.7361^n)$. For connectivity problems in which the extension algorithm's running time 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.
作者备注：Companion site (including certificates and Lean formalization): https://serggasp.github.io/sample-MLS-site/ ; archived at https://doi.org/10.5281/zenodo.23851002