Dallard–Milanič–Štorgel conjecture on induced-minor-free graphs

The conjecture proposed a tractability route for Maximum Independent Set on graphs excluding a fixed planar graph as an induced minor. The associated question was described as open by Korhonen in 2023.

Known results

• Korhonen (2023): for every fixed planar $H$, Maximum Weight Independent Set has a $2^{O(n/\log^{1/6} n)}$-time algorithm on $H$-induced-minor-free graphs, without resolving the conjecture.
• A 2025 weakening proves polylogarithmic tree-independence after additionally excluding $K_{1,s}$ as an induced subgraph.
• Related 2026 work gives sub-polynomial tree-independence bounds for classes excluding $K_{t,t}$ and a $t\times t$ wall as induced minors, but does not address this conjecture directly.

September 2026 counterexample

Édouard Bonnet and Yeonsu Chang report a fixed planar forbidden induced minor, primarily the $5\times5$ grid, for which Maximum Independent Set remains NP-hard. Their preprint claims this refutes the Dallard–Milanič–Štorgel conjecture and stated weakenings by Gartland–Lokshtanov and Korhonen.

Current status (as of September 2026): The conjecture is claimed refuted by Bonnet and Chang, but the counterexample has not been independently verified in the retrieved record.