MIS FPT in Pℓ(t)-free Graphs

Status open high confidence

Conjecture 2 from arXiv:1909.08426 asserts that MIS is FPT in $P_\ell(t)$-free graphs for all integers $t$ and $\ell$; as of May 2026 it remains open. The source paper itself establishes the $\ell=4$, first-coordinate-1 case (MIS FPT in $P(1,t,t,t)$-free graphs for every fixed $t\geq 1$). The smallest explicitly open instance, P$_7$-free graphs ($t=1$, $\ell=7$), is still not known to be FPT; a 2025 ISAAC paper proves polynomial-time tractability of CMSO$_2$-definable problems (including MIS) in P$_7$-free graphs of bounded clique number, which is a weaker and structurally different result from FPT on all P$_7$-free graphs.

Cited literature (1)

• partial Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number (2025)
  authors not retrieved · ISAAC 2025 (LIPIcs) · doi:10.4230/LIPIcs.ISAAC.2025.20

  Proves polynomial-time algorithms for CMSO₂-definable problems including MIS on P₇-free graphs of bounded clique number, extending prior quasipolynomial and polynomial results to this restricted subclass but not resolving FPT for general P₇-free graphs.

Reviewer notes. No follow-up paper resolving the full conjecture or proving FPT for general P₇-free graphs was found across five web searches. The 2025 ISAAC paper (verified via WebFetch) makes progress on P₇-free graphs of bounded clique number in polynomial time, but does not cite 1909.08426 explicitly and addresses a different complexity notion than FPT. Authors of the ISAAC 2025 paper were not retrieved. The conjecture is relatively recent (~6 years) and the absence of resolution in the literature supports high-confidence open status.

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