MIS sub-polynomial approximation in H-free graphs

Conjecture 5 (Improved Approximation Conjecture) · arXiv:2004.12166

arXiv Conjecture high confidence— first stated 2020-04-25

Authors: Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant

Status open medium confidence

No follow-up paper resolving or disproving Conjecture 5 from arXiv:2004.12166 was found after targeted searches. The conjecture remains open: it is known to hold for all H whose H-free class admits a polynomial-time MIS algorithm (e.g., P_6-free, fork-free graphs) by closure under graph substitution, but the full statement for every graph H is unresolved. The internal candidate reference arXiv:2301.10147 addresses the classical Erdős-Hajnal conjecture (clique/stable-set size bounds) and does not bear on the algorithmic/approximation formulation.

Reviewer notes. Searches returned only the source paper (ESA 2020), closely related prior work on quasi-PTAS for MIS in H-free graphs (Chudnovsky et al. 2020), and a parameterized inapproximability paper in H-free graphs (Algorithmica 2022) whose content could not be verified due to a paywall redirect. Confidence is medium rather than high because the conjecture is ~6 years old, making absence of indexed progress mildly suspicious, though no counterexample or proof was found.

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

Conjecture. Every graph $H$ satisfies the improved approximation property, i.e., there exists a constant $\varepsilon > 0$ such that MIS admits a (randomized) $n^{1-\varepsilon}$-approximation polynomial algorithm on every $H$-free $n$-vertex graph $G$.

Context

This conjecture is introduced as an algorithmic weakening of the Erdős-Hajnal conjecture. It states informally that the inapproximability of MIS in general graphs can always be beaten in any proper hereditary class. It is strictly weaker than the Erdős-Hajnal conjecture, since MIS is polynomial in $P_6$-free graphs while it is open whether $P_5$ satisfies the Erdős-Hajnal property.

Source paper

An algorithmic weakening of the Erdős-Hajnal conjecture
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant · 2020-04-25
https://arxiv.org/abs/2004.12166 PDF source