MIS parameterized complexity in H-free graphs

Parameterized MIS Dichotomy · arXiv:1909.08426

arXiv Problem high confidence— first stated 2019-09-18

Authors: Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant

Status partial high confidence

The full FPT vs W[1]-hard dichotomy for MIS in H-free graphs remains open as of 2026. Significant partial progress has been made: the dichotomy is completely resolved for all 4-vertex forbidden subgraphs, and many 5-vertex cases are settled, but cases such as P7-free, S_{1,1,3}-free, and S_{1,2,2}-free graphs remain open. A 2020 follow-up by Dvořák et al. strengthened hardness results by proving parameterized inapproximability lower bounds under ETH/Gap-ETH for graph classes where W[1]-hardness was already known, without resolving new FPT cases.

Cited literature (1)

partial Parameterized Inapproximability of Independent Set in H-Free Graphs (2020)

Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski · Algorithmica · arXiv:2006.10444 · doi:10.1007/s00453-022-01052-5

Under ETH and Gap-ETH, strengthens existing W[1]-hardness results for MIS in H-free graphs to parameterized inapproximability lower bounds, and extends inapproximability to K_{a,b}-free graphs, but does not settle new FPT cases or the full dichotomy.

Reviewer notes. The precursor paper arXiv:1810.04620 (Bonnet, Bousquet, Charbit, Thomassé, Watrigant, 2018) initiated the systematic classification and predates the source paper; it is not listed in since_posted. The source paper itself (1909.08426) establishes additional FPT cases (disjoint unions of cliques, P(1,t,t,t)-free, dart-free, cricket-free). No paper found resolving the full dichotomy for all H as of the search date.

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

Problem. Is MIS (randomized) FPT or $W[1]$-hard in $H$-free graphs?

Context

This is the parameterized counterpart of the classical MIS dichotomy question. Alekseev's NP-hardness reduction does not transfer to $W[1]$-hardness, leaving a priori more candidate graphs $H$ for which the parameterized status is open. Dabrowski et al. initiated a systematic study of this question.

Notes. PDF source. Formally labelled with a bullet marker in the paper alongside the conjectures.

Source paper

When Maximum Stable Set can be solved in FPT time
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant · 2019-09-18
https://arxiv.org/abs/1909.08426 PDF source