Sparse induced subgraphs in P6-free graphs

Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski

Research output: Contribution to conferencePaperpeer-review

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.

Original languageEnglish (US)
Pages5291-5299
Number of pages9
DOIs
StatePublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024

Conference

Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States
CityAlexandria
Period1/7/241/10/24

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Sparse induced subgraphs in P6-free graphs'. Together they form a unique fingerprint.

Cite this