TY - GEN
T1 - Sparse Induced Subgraphs in P7-Free Graphs of Bounded Clique Number
AU - Chudnovsky, Maria
AU - Czyżewska, Jadwiga
AU - Kluk, Kacper
AU - Pilipczuk, Marcin
AU - Rzążewski, Paweł
N1 - Publisher Copyright:
© Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, and Paweł Rzążewski.
PY - 2025
Y1 - 2025
N2 - 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 CMSO2 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 P6-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 P7-free graphs of bounded clique number.
AB - 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 CMSO2 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 P6-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 P7-free graphs of bounded clique number.
KW - maximum weight independent set
KW - maximum weight induced subgraph
KW - P-free graphs
UR - https://www.scopus.com/pages/publications/105031381065
UR - https://www.scopus.com/pages/publications/105031381065#tab=citedBy
U2 - 10.4230/LIPIcs.ISAAC.2025.20
DO - 10.4230/LIPIcs.ISAAC.2025.20
M3 - Conference contribution
AN - SCOPUS:105031381065
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Algorithms and Computation, ISAAC 2025
A2 - Chen, Ho-Lin
A2 - Hon, Wing-Kai
A2 - Tsai, Meng-Tsung
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th International Symposium on Algorithms and Computation, ISAAC 2025
Y2 - 7 December 2025 through 10 December 2025
ER -