{"id":"arxiv/2609.11285","url":"https://arxiv.org/abs/2609.11285","tags":["cs.CC","cs.DM","cs.DS","math.CO"],"score":0,"title":"Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor","domain":"cs.CC","source":"arxiv","authors":["Édouard Bonnet","Yeonsu Chang"],"reviews":0,"subject":"cs.CC","summary":"We show that there is a fixed planar graph $H$, namely the $5 \\times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This refutes the Dallard--Milanič--Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}