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

CREATORBenjamin Bergougnoux, Vera Chekan, Giannos Stamoulis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE292 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19793

Browse the full library · About the Tower of Babel