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

Abstract

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.

8 pages, 6 figures