FPT candidates for H-free MIS nearly all tractable

Status open medium confidence

The informal belief that almost all connected graphs H satisfying the structural conditions of Figure 1 in arXiv:1909.08426 will yield (randomized) FPT algorithms for Maximum Independent Set in H-free graphs remains unresolved. Post-2019 searches confirm that the classical open cases—P7-free, S_{1,1,3}-free, and S_{1,2,2}-free graphs—still lack FPT algorithms, suggesting that at least some FPT candidates are genuinely difficult. Related work has expanded FPT/polynomial results to adjacent settings (e.g., induced-minor exclusion), but the core informal conjecture about induced-subgraph exclusion is not settled.

Cited literature (1)

• partial Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 ⊎ C_4 (2023)
  Bonnet, Édouard; Duron, Julien; Geniet, Colin; Thomassé, Stéphan; Wesolek, Alexandra · ESA 2023 / Algorithmica 2025 · arXiv:2302.08182 · doi:10.4230/LIPIcs.ESA.2023.23

  Extends MIS tractability to graphs excluding certain induced minors (K_1+tK_2 and tC_3⊎C_4), a related but distinct framework from induced-subgraph exclusion; does not directly resolve the open H-free cases from arXiv:1909.08426.

Reviewer notes. The conjecture is deliberately informal ('there will be very few connected candidates ... which will not end up in (randomized) FPT'), making it hard to falsify definitively. Post-2019 literature confirms that P7-free, S_{1,1,3}-free, and S_{1,2,2}-free graphs remain major open cases within the FPT-candidate class, so the informal optimism has not been borne out for all candidates. No paper was found that explicitly claims to settle or refute this belief. The 2302.08182 paper (ESA 2023, Algorithmica 2025) by some of the same authors extends tractability results to excluded induced minors, but that is a separate framework.

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