A polynomial excluded-minor approximation of treedepth (Q2119392)

Summary: 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 \textit{C. Chekuri} and \textit{J. Chuzhoy} [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 60--69 (2014; Zbl 1315.05131)] 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)\): i) a \(k \times k\) grid, ii) a complete binary tree of height \(k\), or iii) a path of order \(2^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 [\textit{B. Rossman}, LIPIcs -- Leibniz Int. Proc. Inform. 67, Article 27, 17 p. (2017; Zbl 1402.68077)], which was the original motivation for our investigation of treedepth.