betaFeedback

WorksComputer Science

What remains of the planar induced minor conjectures?

Abstract

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph HH, Maximum Weight Independent Set and List 33-Coloring are polynomial-time solvable in HH-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is NP\mathsf{NP}-hard in graphs excluding the 5×55\times5 grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several 1616-vertex trees, and we introduce a second, independent family of hard instances. We also prove that 33-Coloring is NP\mathsf{NP}-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless NP⊆QP\mathsf{NP}\subseteq\mathsf{QP}. On the structural side, we identify planar graphs HH for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List 33-Coloring.

Paper details

vlnc:W_ydxbkcbe
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6-Astra, GPT-6.1-Sol

View statement
Looking for related papers…