MIS quasipolynomial time for planar induced-minor-free

Question 2 · arXiv:2302.08182

arXiv Question high confidence— first stated 2025-12-31

Authors: Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek

Status open high confidence

Question 2 — whether Max Independent Set is solvable in quasipolynomial time for every planar-H-induced-minor-free graph class — remains open. The source paper itself adds the $tC_3 \uplus C_4$ case to the growing list of positive instances (already including $C_t$- and $tC_3$-free cases). A February 2026 paper (arXiv:2602.18317) extends the family further to $sC_t$-induced-minor-free graphs but only achieves a QPTAS (approximation scheme), not an exact quasipolynomial-time algorithm, so the conjecture for all planar $H$ is unresolved.

Cited literature (1)

partial QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes (2026)

unknown (arXiv:2602.18317) · arXiv preprint · arXiv:2602.18317

Proves a quasipolynomial-time approximation scheme (QPTAS) for MWIS in graphs excluding $sC_t$ as an induced minor, generalising the $C_4 \uplus sC_3$ case, but achieves only approximate (not exact) computation and does not cover all planar $H$.

Reviewer notes. No paper found that resolves Question 2 for all planar $H$. The Gartland–Lokshtanov conjecture (polynomial-time for all planar-H-induced-minor-free classes) is described in arXiv:2602.18317 as 'notoriously open', which subsumes Question 2. Progress is incremental: new planar forbidden graphs are handled one family at a time.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Is it true that for every planar graph $H$, Max Independent Set can be solved in quasipolynomial time in the class of graphs excluding $H$ as an induced minor?

Context

Question 2 is the quasipolynomial-time relaxation of Question 1, for which substantially more positive evidence exists: quasipolynomial-time algorithms are known for $C_t$-induced-minor-free graphs and for $tC_3$-induced-minor-free graphs. The present paper contributes a quasipolynomial-time algorithm for $tC_3 \uplus C_4$-induced-minor-free graphs, running in $n^{O(t^{2}\log n)+f(t)}$.

Notes. No parenthetical attribution appears in the theorem header; treated as the paper authors' own question. It is the natural quasipolynomial companion to Question 1.

Source paper

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek · 2025-12-31
https://arxiv.org/abs/2302.08182