PTAS for monotone FO optimization via local search

Open Problem (Section 1.1) · arXiv:1901.01797

arXiv Problem medium confidence— first stated 2019-01-07

Status partial medium confidence

The open problem asks whether a local search variation yields PTAS for all monotone first-order optimization problems on classes with strongly sublinear separators. Dvořák's follow-up work (arXiv:2103.08698, SWAT 2022) obtains PTAS for fractionally treewidth-fragile classes (which include all common strongly sublinear separator classes) and a QPTAS for all strongly sublinear separator classes, via Baker-style decomposition techniques rather than local search. The specific question about the local search approach remains unresolved, and PTAS for the full generality of strongly sublinear separator classes (beyond fractionally treewidth-fragile ones) is still open.

Cited literature (1)

partial Approximation metatheorems for classes with bounded expansion (2021)

Zdeněk Dvořák · SWAT 2022 (LIPIcs vol. 227) · arXiv:2103.08698 · doi:10.4230/LIPIcs.SWAT.2022.22

Proves PTAS for monotone FO maximization in fractionally treewidth-fragile classes and QPTAS in all strongly sublinear separator classes, via Baker-style techniques rather than local search; the local search question and full PTAS for all strongly sublinear separator classes remain open.

Reviewer notes. The follow-up paper 2103.08698 makes substantial progress by obtaining PTAS for many of the target classes, but does so via Baker-style decompositions rather than local search. Whether a local search variation specifically achieves PTAS for all monotone FO problems on all strongly sublinear separator classes remains an open question.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. It is an open problem whether some variation on the local search approach can give PTAS for all monotone FO optimization problems.

Context

Cabello–Gajser and Har-Peled–Quanrud showed that the trivial local search algorithm (performing bounded-size changes on an initial solution as long as it can be improved) gives PTASes for maximum independent set and minimum dominating set, as well as many related problems, on classes with strongly sublinear separators. The question is whether this approach, or a variation thereof, can be extended to cover all monotone first-order optimization problems on such classes.

Notes. Stated as prose ('It is an open problem whether…') in Section 1.1 without a labelled theorem environment; no prior attribution given. PDF source — remainder of paper text is cut off, so additional items later in the paper may be missing.

Source paper

Baker game and polynomial-time approximation schemes
Zdeněk Dvořák · 2019-01-07
https://arxiv.org/abs/1901.01797 PDF source