Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)Research Paper
Graphs excluding a fixed planar graph as a minor have bounded treewidth (Robertson–Seymour 1986), so every problem expressible in monadic second-order logic, Max Independent Set included, is polynomial on them. The analogous statement for induced minors, obtained by deleting vertices and contracting edges but never deleting edges, fails for problems such as…