MIS complexity for S_{i,j,k}-free graphs with P₇

Maximum Independent Set complexity for H-free graphs when H contains P7, S1,1,3, or S1,2,2 · arXiv:2001.01607

arXiv Problem medium confidence— first stated 2020-10-27

Authors: Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon

Status partial medium confidence

The computational complexity of Maximum Independent Set for $H$-free graphs when $H$ contains $P_7$, $S_{1,1,3}$, or $S_{1,2,2}$ remains unresolved as a full polynomial/NP-hard dichotomy. Partial progress exists: quasi-polynomial-time algorithms apply to all $P_k$-free graphs (hence $P_7$-free), and polynomial-time algorithms have been obtained for bounded-degree graphs excluding any fixed subdivided claw as an induced subgraph, covering $S_{1,1,3}$- and $S_{1,2,2}$-free cases under bounded degree. No polynomial-time algorithm or NP-hardness result for the general unbounded-degree cases has been found.

Cited literature (1)

partial Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws (2022)

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Paweł Rzążewski · arXiv preprint · arXiv:2107.05434

Gives a polynomial-time algorithm for Maximum Independent Set in $H$-free graphs of bounded degree for any fixed subdivided claw $H$, resolving the bounded-degree special cases of $S_{1,1,3}$- and $S_{1,2,2}$-free graphs but not the general (unbounded-degree) question.

Reviewer notes. Quasi-polynomial-time algorithms for Independent Set in P_k-free graphs (Gartland–Lokshtanov 2020, arXiv:2005.00690; Pilipczuk et al. 2021, arXiv:2009.13494) provide sub-exponential progress for P_7-free graphs but fall short of polynomial time. The bounded-degree result (arXiv:2107.05434) makes partial inroads on the S_{i,j,k} cases. The full dichotomy determining which S_{i,j,k} yield polynomial-time solvability vs NP-hardness remains open. The internal reference 2203.06775 was verified to be about a different conjecture in the same source paper (treewidth of (even hole, K_4)-free graphs, Conjecture 1.5), not the MIS complexity problem.

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

Problem. Determine the computational complexity of the Maximum Independent Set problem for $H$-free graphs whenever $H$ is some $S_{i,j,k}$ that contains either $P_7$, $S_{1,1,3}$, or $S_{1,2,2}$.

Context

The problem is polynomial for $H \subseteq P_k$ with $k \leq 6$ and for $H \subseteq S_{i,j,k}$ with $(i,j,k) \leq (1,1,2)$, and is NP-hard when $H$ is not an induced subgraph of any $S_{i,j,k}$. The boundary region where $H$ contains $P_7$, $S_{1,1,3}$, or $S_{1,2,2}$ is listed as completely open.

Notes. PDF source — math notation reconstructed; stated in the 'Algorithmic consequences' section.

Source paper

(Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 2 : bounds on treewidth
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon · 2020-10-27
https://arxiv.org/abs/2001.01607 PDF source