Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor
Abstract
We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the 5 × 5 grid as an induced minor. This negatively answers a question of Dallard--Milanič--Štorgel that has attracted sustained attention, and refutes a conjecture by Gartland and Lokshtanov. Unless N-variable 3-SAT can be solved in time 2𝒪(N1−ε) for some ε > 0, MIS requires 2Ω(n1/2−o(1)) time on n-vertex graphs in this class. This complements a 2Õ(n2/3)-time algorithm on any H-induced-minor-free class by Korhonen and Lokshtanov. Exploiting a connection between low twin-width or reduced parameters on one hand and planar-induced-minor-freeness on the other, we further show that 3-Coloring, Feedback Vertex Set and Dominating Set are NP-complete on weakly sparse graphs of reduced component max-leaf (hence twin-width) at most 3, even when a witnessing contraction sequence is given. Classes of bounded reduced component max-leaf (by any constant) and of twin-width at most 3 are known to exclude a fixed planar graph as an induced minor. The 3-Coloring and Feedback Vertex Set results refute more cases of the Gartland--Lokshtanov conjecture, even when the inputs are weakly sparse. The complexity of MIS in weakly sparse graphs excluding a planar induced minor remains open.
Related
- An improved bound on the treewidth of planar graphs excluding a grid minor
- Asymptotic dimension of graphs excluding an induced or fat minor
- Unavoidable flats in matroids excluding a uniform minor
- Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
- Minor exclusion and planar rigidity
BibTeX
@misc{bonnet2026independent,
title = {{Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor}},
author = {Édouard Bonnet and Yeonsu Chang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11285},
eprint = {2609.11285},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11285},
}
RIS
TY - UNPB
TI - Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor
AU - Édouard Bonnet
AU - Yeonsu Chang
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11285
UR - https://arxiv.org/abs/2609.11285
AB - We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the 5 × 5 grid as an induced minor. This negatively answers a question of Dallard--Milanič--Štorgel that has attracted sustained attention, and refutes a conjecture by Gartland and Lokshtanov. Unless N-variable 3-SAT can be solved in time 2^𝒪(N^1−ε) for some ε > 0, MIS requires 2^Ω(n^1/2−o(1)) time on n-vertex graphs in this class. This complements a 2^Õ(n^2/3)-time algorithm on any H-induced-minor-free class by Korhonen and Lokshtanov. Exploiting a connection between low twin-width or reduced parameters on one hand and planar-induced-minor-freeness on the other, we further show that 3-Coloring, Feedback Vertex Set and Dominating Set are NP-complete on weakly sparse graphs of reduced component max-leaf (hence twin-width) at most 3, even when a witnessing contraction sequence is given. Classes of bounded reduced component max-leaf (by any constant) and of twin-width at most 3 are known to exclude a fixed planar graph as an induced minor. The 3-Coloring and Feedback Vertex Set results refute more cases of the Gartland--Lokshtanov conjecture, even when the inputs are weakly sparse. The complexity of MIS in weakly sparse graphs excluding a planar induced minor remains open.
ER -