Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor

Édouard Bonnet, Yeonsu Chang

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 Dalla…