Answers are grounded in this paper and cite their sources.
Demonstrates a quasipolynomial-time approximation for MWIS in graphs, suggesting potential for broader applications.
We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (MWIS) in graphs with a bounded number of pairwise vertex-disjoint and non-adjacent long induced cycles. More formally, for every fixed s and t, we show a QPTAS for MWIS in graphs that exclude sC_t as an induced minor. Combining this with known results, we obtain a QPTAS for the problem of finding a largest induced subgraph of bounded treewidth with given hereditary property definable in Counting Monadic Second Order Logic, in the same classes of graphs. This is a step towards a conjecture of Gartland and Lokshtanov which asserts that for any planar graph H, graphs that exclude H as an induced minor admit a polynomial-time algorithm for the latter problem. This conjecture is notoriously open and even its weaker variants are confirmed only for very restricted graphs H.
No takes yet. Share an insight, caveat, or question.
Bonnet et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: