2026-10-02T08:23:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26045 2026-09-23T23:58:40Z ddc:004 open_access

QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes Bonnet, Édouard Czyżewska, Jadwiga Masařík, Tomáš Pilipczuk, Marcin Rzążewski, Paweł independent set long holes QPTAS induced subgraphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Jadwiga Czyżewska and Tomáš Masařík and Marcin Pilipczuk and Paweł Rzążewski 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.9 urn:nbn:de:0030-drops-260454 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode