Conference Paper,
Sparse induced subgraphs in P-free graphs
Affiliations
- [1] Princeton University [NORA names: United States; America, North; OECD];
- [2] Institute of Informatics [NORA names: Poland; Europe, EU; OECD];
- [3] IT University of Copenhagen [NORA names: ITU IT University of Copenhagen; University; Denmark; Europe, EU; Nordic; OECD];
- [4] Warsaw University of Technology [NORA names: Poland; Europe, EU; OECD]
Abstract
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of P6-free graphs. This generalizes the work of Grzesik, Klimošová, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in P6-free graphs [SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rzążewski, and Seymour on problems in P5-free graphs [SODA 2021]. The key step is a new generalization of the framework of potential maximal cliques. We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their carvers: vertex sets that contain the same vertices from the sought solution and have similar separation properties.