Independent set APX-hardness without sublinear separators

Open Problem (Section 1.2): APX-hardness on classes without sublinear separators · arXiv:1704.00125

arXiv Problem medium confidence— first stated 2017-04-01

Status open high confidence

Dvořák asks whether maximum independent set is APX-hard on every subgraph-closed graph class that lacks sublinear separators (or at least has exponential expansion). No follow-up paper proving or disproving this was found after an exhaustive search. Related positive results (PTAS, QPTAS for bounded-expansion and sublinear-separator classes) confirm the structural boundary the problem targets, but the hardness side remains unresolved as of 2026.

Reviewer notes. No follow-up resolving the hardness question was found in 5 web calls. The conjecture sits at the boundary between tractability (PTAS on classes with strongly sublinear separators) and hardness (APX-hard on 3-regular graphs, which have no sublinear separators); the intermediate regime—subgraph-closed classes with exponential expansion but no 3-regular graphs—appears untouched in the indexed literature.

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

Problem. It would be interesting to see whether this intuition can be made precise and for example show that the maximum independent set problem is APX-hard on any subgraph-closed class of graphs that does not have sublinear separators (or at least has exponential expansion).

Context

The paper notes that maximum independent set is APX-hard on bounded-degree graphs, so results cannot extend to classes containing all 3-regular graphs. Classes studied all have strongly sublinear separators; the authors ask whether APX-hardness can be proved for any subgraph-closed class lacking this property.

Notes. Stated as an open research question in prose; no labelled theorem environment.

Source paper

Thin graph classes and polynomial-time approximation schemes
Zdeněk Dvořák · 2017-04-01
https://arxiv.org/abs/1704.00125 PDF source