MWIS complexity in P₇-free graphs

Status partial high confidence

The full complexity of Maximum Weight Independent Set in P7-free graphs remains open. Gartland and Lokshtanov (FOCS 2020) established a quasi-polynomial time algorithm running in n^{O(k^2 log^3 n)} for all Pk-free graphs (including P7-free), the first super-polynomial upper bound beyond NP-hardness evidence. More recently, Chudnovsky, Czyzewska, Kluk, Pilipczuk, and Rzazewski (ISAAC 2025) extended polynomial-time tractability to P7-free graphs of bounded clique number. The full polynomial-time resolution for all P7-free graphs remains open as of 2026.

Cited literature (2)

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

  Gives a quasi-polynomial time algorithm (n^{O(k^2 log^3 n)}) for Maximum Weight Independent Set on Pk-free graphs for any fixed k, directly applying to P7-free graphs but not achieving polynomial time.

• partial Sparse Induced Subgraphs in P_7-Free Graphs of Bounded Clique Number (2025)
  Maria Chudnovsky, Jadwiga Czyzewska, Kacper Kluk, Marcin Pilipczuk, Pawel Rzazewski · ISAAC 2025 · doi:10.4230/LIPIcs.ISAAC.2025.20

  Extends polynomial-time tractability of MWIS and related sparse induced subgraph problems to P7-free graphs of bounded clique number, but the general P7-free case remains open.

Reviewer notes. General P7-free case still open (no polynomial-time algorithm known). Two verified partial advances since posting: quasi-polynomial time for all Pk-free graphs (Gartland-Lokshtanov, FOCS 2020, arXiv:2005.00690) and polynomial time for P7-free graphs restricted to bounded clique number (Chudnovsky et al., ISAAC 2025, LIPIcs). A polynomial-time algorithm for P6-free graphs was also achieved circa SODA 2024, but that is for a smaller graph class and was not directly verified here.

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