MIS dichotomy for path- and claw-subdivision-free graphs

Classical MIS Dichotomy Conjecture · arXiv:1909.08426

arXiv Conjecture medium confidence— first stated 2019-09-18

Authors: Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant

Status partial high confidence

The conjecture that MIS in H-free graphs is in P if and only if H is a path or subdivided claw remains open at the polynomial-time level. The landmark post-2019 development is arXiv:2305.15738 (Gartland, Lokshtanov, Masařík, M. Pilipczuk, M. Pilipczuk, Rzążewski; STOC 2024), which proves MWIS is solvable in quasi-polynomial time for every H-free graph class where H is a path or subdivided claw, closing the gap between predicted-tractable cases and NP-hardness. Polynomial-time algorithms are established for specific subclasses (P_t-free for t ≤ 6, fork-free/S_{1,1,2}-free), but polynomial-time solvability for all S_{i,j,k}-free graphs remains open.

Cited literature (1)

partial Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time (2023)

Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski · Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024) · arXiv:2305.15738 · doi:10.1145/3618260.3649791

Proves that MWIS is solvable in quasi-polynomial time on H-free graphs whenever each connected component of H is a path or a subdivided claw, showing all conjectured-tractable cases are not NP-hard but stopping short of the conjectured polynomial-time bound.

Reviewer notes. The quasi-polynomial result of arXiv:2305.15738 is the major post-2019 development: it shows all cases predicted tractable by the conjecture are at worst quasi-polynomial, confirming the NP-hard/tractable boundary but not yet establishing polynomial time for the full class S_{i,j,k}-free. No paper resolving the full polynomial-time dichotomy was found.

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

Conjecture. For every connected graph $H$, Maximum Independent Set in $H$-free graphs is in $\mathsf{P}$ if and only if $H \in \{P_\ell\}_{\ell} \cup \{S_{i,j,k}\}_{i \leq j \leq k}$.

Context

The polynomial-time complexity of MIS in $H$-free graphs has been studied since the early 1980s. Alekseev showed that if $H$ is neither a path nor a subdivided claw then MIS is NP-complete on $H$-free graphs, motivating this conjecture about the full dichotomy. The authors note that an even stronger conjecture is postulated by Lozin [28].

Notes. PDF source — math may be garbled. $\{P_\ell\}_\ell$ denotes the family of paths and $\{S_{i,j,k}\}_{i \leq j \leq k}$ denotes the family of subdivided claws. Presented as a conjecture formalising a well-known open problem; no explicit citation in the header.

Source paper

When Maximum Stable Set can be solved in FPT time
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant · 2019-09-18
https://arxiv.org/abs/1909.08426 PDF source