Sparse induced subgraphs in P_6-free graphs

July 14, 2023 Β· Declared Dead Β· πŸ› ACM-SIAM Symposium on Discrete Algorithms

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, MichaΕ‚ Pilipczuk, PaweΕ‚ RzΔ…ΕΌewski arXiv ID 2307.07330 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM, math.CO Citations 5 Venue ACM-SIAM Symposium on Discrete Algorithms Last Checked 4 months ago
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 $P_6$-free graphs. This generalizes the work of Grzesik, KlimoΕ‘ovΓ‘, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in $P_6$-free graphs~[SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, RzΔ…ΕΌewski, and Seymour on problems in $P_5$-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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted