A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis · 2025
Read A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space by Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis (2025) 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-2510-19793.txt.
Introduction
Benjamin Bergougnoux, Vera Chekan, and Giannos Stamoulis prove a meta-theorem: any problem expressible in a logic they design can be solved fast on graphs of small treedepth. Treedepth measures how shallowly a graph can be decomposed into a forest. Their logic extends a fragment of monadic second-order logic with operators for neighborhoods, connectivity, acyclicity, and cliques.
The model-checking algorithm runs in single-exponential time in the treedepth and polynomial space, unifying and extending many known tractability results for hard problems like Independent Set and Hamiltonian Cycle. A restricted fragment cuts the space down to near-logarithmic in the graph size factor. Along the way the logic captures satisfiability and several modulo counting problems, so the theorem hands those problems new algorithms.
Catalog record
| CREATOR | Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 292 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-19793