MIS approximation exponent in H-free graphs

Question: optimal approximation exponent for MIS in H-free graphs · arXiv:2004.12166

arXiv Informal medium confidence— first stated 2020-04-25

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

Status open high confidence

The question of determining the largest ε > 0 such that MIS admits an O(n^{1-ε})-approximation in H-free graphs remains open for most choices of H. The source paper itself proved tight bounds for specific classes: a √OPT-approximation for C_4-free graphs (from local search applied to K_{t,t}-free), and matching upper and lower bounds for triangle-free and high-girth graphs (tight up to constants in the exponent c/γ). No subsequent paper has been found that resolves the meta-question of characterising the optimal exponent as a function of H in full generality.

Reviewer notes. No follow-up paper directly addressing the optimal approximation exponent as a function of H was found. Related nearby work exists: (1) arXiv:2006.10444 (Bonnet, Giannopoulos, Kim, Rzążewski, Sikora, Algorithmica 2022) studies parameterised inapproximability of independent set in H-free graphs — this is FPT inapproximability rather than the polynomial-time exponent question and was not fetched to verify; (2) a STACS 2023 paper on approximating inapproximable problems on bounded-twin-width graphs was noted but not verified. The question is a fine-grained open problem within a line of work that remains very active.

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

Informal. For a given $H$, what is the largest $\varepsilon > 0$ such that MIS admits an $O(n^{1-\varepsilon})$-approximation algorithm in $H$-free graphs?

Context

After establishing that many graphs $H$ satisfy the improved approximation property, the authors ask how to optimise the approximation ratio. They investigate this in Sections 3 and 4, proving e.g. a $\sqrt{OPT}$-approximation in $C_4$-free graphs and a tight inapproximability bound in triangle-free and high-girth graphs.

Notes. Posed as an open research direction in running prose in the 'Results and organization' section; partially investigated within the paper but not fully resolved.

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