{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicsxp2hdq7wvmlxzl5l75w5pjufpanxkdhtab2c47rvphliafsdrq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfj46iv76hn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.18317v1",
  "publishedAt": "2026-02-23T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Édouard Bonnet",
    "Jadwiga Czyżewska",
    "Tomáš Masařík",
    "Marcin Pilipczuk",
    "Paweł Rzążewski"
  ],
  "textContent": "**Authors:** Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski\n\nWe 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"
}