FPT MIS in P(t,t,t,t)-free graphs

Conjecture 1 · arXiv:1909.08426

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

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

Status open medium confidence

The conjecture asks whether MIS is FPT in P(t,t,t,t)-free graphs for any fixed integer t. The source paper (arXiv:1909.08426) provides partial progress by proving the special case P(1,t,t,t)-free graphs. A wide search across arXiv, Semantic Scholar, and general web sources (covering up to 2025) found no follow-up paper resolving the full conjecture; the problem remains open after six years.

Reviewer notes. No follow-up resolving Conjecture 1 found. The conjecture is ~6 years old (2019), making medium confidence appropriate: the search was thorough but absence of evidence for an older conjecture is mildly suspicious. The only known progress remains the P(1,t,t,t)-free special case proved in the source paper itself. The journal version of the related H-free complexity dichotomy paper (Bonnet et al., Algorithmica 2021, arXiv:1810.04620) was found but does not address P(t,t,t,t)-free graphs.

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

Conjecture. For any integer $t$, MIS can be solved in FPT time in $P(t,t,t,t)$-free graphs.

Context

MIS was already shown FPT on $P(t,t,t)$-free graphs; this conjecture proposes the natural next step for four-vertex paths with clique substitutions. The present paper proves the special case $P(1,t,t,t)$-free graphs as partial progress toward Conjecture 1.

Notes. PDF source.

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