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

CREATORMaria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Paweł Rzążewski
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE179 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14836

Browse the full library · About the Tower of Babel