Indexed metadata
Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor
Édouard Bonnet, Yeonsu Chang
Source abstract
We show that there is a fixed planar graph , namely the grid, such that Max Independent Set remains NP-hard in -induced-minor-free graphs. This refutes the Dallard--Milanič--Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.