PTAS for weighted Minimum Vertex Cover in fragile classes

Open Problem: PTAS for weighted minimization problems in fractionally treewidth-fragile classes · arXiv:2105.01780

arXiv Problem medium confidence— first stated 2021-05-04

Authors: Zdeněk Dvořák, Abhiruk Lahiri

Status open high confidence

The open problem asks whether a PTAS exists for weighted Minimum Vertex Cover (and more generally for distance-1 minimization problems) in fractionally treewidth-fragile graphs or hereditary classes with sublinear separators. The main obstruction is that the local-search technique that handles the unweighted case does not extend to weighted instances. A closely related subsequent paper by Dvořák (arXiv:2103.08698, SWAT 2022) gives approximation metatheorems for monotone maximization problems in these classes but explicitly restricts to maximization and does not resolve the minimization question. No paper found in the indexed literature as of May 2026 settles this problem.

Reviewer notes. No follow-up resolving this open problem was found after an exhaustive 5-call web search. The most related post-2021 work is arXiv:2103.08698 (Dvořák, SWAT 2022) which proves approximation metatheorems for monotone *maximization* problems in fractionally treewidth-fragile classes, but explicitly does not cover minimization problems. The structural paper arXiv:2208.10074 (product structure of classes with strongly sublinear separators) is also related but contains no algorithmic results for vertex cover. The conjecture is recent (2021) and the absence of follow-up in the literature supports an open status with high confidence.

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

Problem. For the minimization problems, we do not know whether fractional treewidth-fragility is sufficient even for the distance-1 problems. In particular, consider the Minimum Vertex Cover problem in fractionally treewidth-fragile graphs, or more generally in hereditary classes with sublinear separators: while the unweighted version can be dealt with by the local search method, we do not know whether there exists a PTAS for the weighted version of this problem.

Context

The paper's main results (Theorem 2 and its corollaries) apply exclusively to maximization problems; the authors extend fractional treewidth-fragility techniques to handle bounded-distance dependencies for near-monotone maximization. For minimization problems the analogous question is left open, with weighted Minimum Vertex Cover in fractionally treewidth-fragile (or sublinear-separator) classes offered as a concrete test case.

Notes. Stated in running prose without a labelled environment; PDF extraction — surrounding math is clean but statement itself is purely verbal.

Source paper

Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs
Zdeněk Dvořák, Abhiruk Lahiri · 2021-05-04
https://arxiv.org/abs/2105.01780 PDF source