Polynomial-time MIS on Pₜ-free graphs

Status partial high confidence

The conjecture remains open in its full generality for all $t \geq 7$. The most significant post-2019 advance is the quasi-polynomial-time algorithm of Gartland and Lokshtanov (2020), which shows that Maximum Independent Set on $P_k$-free graphs can be solved in time $n^{O(k^2 \log^3 n)}$ for any fixed $k$, ruling out NP-completeness for any fixed path length. Polynomial-time results have been extended to $P_7$-free graphs with bounded clique number (ISAAC 2025), but polynomial-time solvability for general $P_t$-free graphs with $t \geq 7$ remains open.

Cited literature (1)

• partial Independent Set on $P_k$-Free Graphs in Quasi-Polynomial Time (2020)
  Peter Gartland, Daniel Lokshtanov · arXiv preprint · arXiv:2005.00690

  Proves that Maximum Weight Independent Set on $P_k$-free graphs is solvable in quasi-polynomial time $n^{O(k^2 \log^3 n)}$ for any fixed $k$, providing the first conclusive evidence that the problem is not NP-complete for any fixed $k$ and representing the strongest known upper bound for $t \geq 7$.

Reviewer notes. The quasi-polynomial-time result of Gartland--Lokshtanov (arxiv:2005.00690) is the main post-2019 advance directly relevant to this problem; it does not achieve polynomial time but establishes a clear barrier to NP-hardness. A 2025 ISAAC paper (DOI 10.4230/LIPIcs.ISAAC.2025.20, 'Sparse Induced Subgraphs in P_7-Free Graphs of Bounded Clique Number') extends polynomial-time solvability to P_7-free graphs with bounded clique number, but this paper's authors and arxiv ID could not be verified within the web-call budget. The polynomial-time open question for unrestricted P_t-free graphs with t >= 7 is thus confirmed open with high confidence.

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