QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910028085067776 |
|---|---|
| author | Bonnet, Édouard Czyżewska, Jadwiga Masařík, Tomáš Pilipczuk, Marcin Rzążewski, Paweł |
| author_facet | Bonnet, Édouard Czyżewska, Jadwiga Masařík, Tomáš Pilipczuk, Marcin Rzążewski, Paweł |
| contents | We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (\textsc{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 \textsc{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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18317 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | 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ł Data Structures and Algorithms We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (\textsc{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 \textsc{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$. |
| title | QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.18317 |