Gartland–Lokshtanov QPTAS conjecture for induced-minor-free graphs
For every fixed finite graph and every , there is a deterministic quasipolynomial-time algorithm that, given a graph with nonnegative vertex weights and containing no induced minor isomorphic to , outputs an independent set satisfying , where is the maximum weight of an independent set in .
References
- QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators — arXiv — Édouard Bonnet, Yeonsu Chang
Source: arXiv
Progress summary
A new result gives a weaker quasipolynomial approximation for several relevant graph classes, but the conjectured approximation result for all induced-minor-free classes remains open.
The Gartland–Lokshtanov conjecture concerns approximation algorithms for maximum independent set on graphs excluding a fixed graph as an induced minor. The recent work broadens known quasipolynomial-time approximation results but does not establish the full conjecture.
October 2026 QPTAS progress
- Bonnet and Chang report a QPTAS for maximum independent set when graphs exclude as an induced minor, for fixed positive integers ; the paper presents this as a step toward, not a proof of, the conjecture.
- A related September 10, 2026 result establishes NP-hardness when excluding a fixed grid as an induced minor, while explicitly leaving the conjectured QPTAS open.
Current status (as of October 2026): Restricted induced-minor-free classes now have claimed QPTAS results, but the full Gartland–Lokshtanov conjecture remains open.
Solutions 0
No solutions have been posted yet.