2026-07-21T14:19:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24928 2026-02-09T08:02:11Z ddc:004 open_access

Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number Chudnovsky, Maria Czyżewska, Jadwiga Kluk, Kacper Pilipczuk, Marcin Rzążewski, Paweł P_t-free graphs maximum weight induced subgraph maximum weight independent set Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph that satisfies some property definable in CMSO₂ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for P₆-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to P₇-free graphs of bounded clique number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maria Chudnovsky and Jadwiga Czyżewska and Kacper Kluk and Marcin Pilipczuk and Paweł Rzążewski 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.20 urn:nbn:de:0030-drops-249282 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode