FO minimization PTAS in treewidth-fragile classes
Problem 6 · arXiv:2103.08698
Status open high confidence
Problem 6 of arXiv:2103.08698 asks whether monotone minimization problems expressible in first-order logic admit constant-factor approximations in bounded-expansion classes and PTASes in efficiently fractionally treewidth-fragile classes. The source paper itself establishes these results only for maximization problems; the paper explicitly notes that for minimization the error is bounded only by a fraction of the total vertex weight rather than the optimum, leaving both parts of the problem open. No subsequent paper resolving either part was found in a targeted literature search spanning arXiv and conference proceedings through May 2026.
Reviewer notes. No follow-up paper addressing the minimization side of Problem 6 was found. The source paper's own discussion identifies weighted vertex cover in fractionally treewidth-fragile classes as the simplest concrete open case. The related literature on PTAS for sparse general-valued CSPs (e.g. arXiv:2012.12607) works with Max-CSP frameworks and does not resolve the FO-minimization question in bounded-expansion classes.
Context
The paper's techniques apply to minimization problems only with error bounded by a fraction of the total vertex weight rather than the optimal, so constant-factor approximation in bounded-expansion classes and PTASes in fractionally treewidth-fragile classes for minimization remain open. As a concrete simplest case, it is unknown whether a PTAS exists for weighted vertex cover in fractionally treewidth-fragile graph classes.
Source paper
Approximation metatheorems for classes with bounded expansion
Zdeněk Dvořák · 2021-10-09
https://arxiv.org/abs/2103.08698
PDF source