A polynomial excluded-minor approximation of treedepth

  • Ken-ichi Kawarabayashi

    National Institute of Informatics, Tokyo, Japan
  • Benjamin Rossman

    Duke University, Durham, USA
A polynomial excluded-minor approximation of treedepth cover
Download PDF

This article is published open access under our Subscribe to Open model.

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×kk \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 cc such that every graph with treedepth Ω(kc)\Omega(k^c) has at least one of the following minors (each of treedepth at least kk):

  • a k×kk \times k grid,
  • a complete binary tree of height kk, or
  • a path of order 2k2^k.

Moreover, given a graph GG we can, in randomized polynomial time, find an embedding of one of these minors or conclude that treedepth of GG is at most O(kc)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.

Cite this article

Ken-ichi Kawarabayashi, Benjamin Rossman, A polynomial excluded-minor approximation of treedepth. J. Eur. Math. Soc. 24 (2022), no. 4, pp. 1449–1470

DOI 10.4171/JEMS/1133