Sparse induced subgraphs in P 7 P_{7} -free graphs of bounded clique number
Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Paweł Rzążewski · 2024
Read Sparse induced subgraphs in P 7 P_{7} -free graphs of bounded clique number by Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Paweł Rzążewski (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14836.txt.
Introduction
Maria Chudnovsky and co-authors extend fast algorithms for finding large sparse subgraphs. Many hard problems ask for the biggest induced subgraph with a stated sparse trait. Logic formulas can express each such trait in one shared language. Graphs that ban a fixed path as an induced subgraph were hoped to make all these problems easy.
A quasi-polynomial method came first, then a polynomial one for graphs banning a six-vertex path. This work pushes the result to graphs banning a seven-vertex path. The catch is that the clique number must stay bounded. With that bound, every problem in the logic family runs in polynomial time.
Catalog record
| CREATOR | Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Paweł Rzążewski |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 179 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14836