A polynomial excluded-minor approximation of treedepth
Lists
Only you see this
Abstract
Treedepth is a minor-monotone graph invariant in the family of “width measures” that includes treewidth and pathwidth. The characterization and approximation of these invariants in terms of excluded minors has been a topic of interest in the study of sparse graphs. A celebrated result of Chekuri and Chuzhoy (2014) shows that treewidth is polynomially approximated by the largest k \times k grid minor in a graph. In this paper, we give an analogous polynomial approximation of treedepth via three distinct obstructions: grids, balanced binary trees, and paths. Namely, we show that there is a constant c such that every graph with treedepth \Omega(k^c) has at least one of the following minors (each of treedepth at least k ): Moreover, given a graph G we can, in randomized polynomial time, find an embedding of one of these minors or conclude that treedepth of G is at most O(k^c) . This result has applications in various settings where bounded treedepth plays a role. In particular, we describe one application in finite model theory, an improved homomorphism preservation theorem over finite structures [Rossman, 2017], which was the original motivation for our investigation of treedepth.
BibTeX
@article{kawarabayashi2021polynomial,
author = {Ken‐ichi Kawarabayashi and Benjamin Rossman},
title = {{A polynomial excluded-minor approximation of treedepth}},
journal = {Journal of the European Mathematical Society},
year = {2021},
doi = {10.4171/jems/1133},
}Loading related content...