← All problems

Gartland–Lokshtanov QPTAS conjecture for induced-minor-free graphs

For every fixed finite graph HH and every ε>0\varepsilon>0, there is a deterministic quasipolynomial-time algorithm that, given a graph GG with nonnegative vertex weights and containing no induced minor isomorphic to HH, outputs an independent set II satisfying w(I)≥(1−ε)αw(G)w(I)\geq (1-\varepsilon)\alpha_w(G), where αw(G)\alpha_w(G) is the maximum weight of an independent set in GG.

References

Progress summary

Refreshed
Open · progress reported

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 sCtsC_t as an induced minor, for fixed positive integers s,ts,t; 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.

Sources

Solutions 0

No solutions have been posted yet.