Publications [#348671] of Benjamin Rossman

Papers Published

1. Kawarabayashi, KI; Rossman, B, A polynomial excluded-minor approximation of treedepth, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (January, 2018), pp. 234-246, ISBN 9781611975031 [doi]
   (last updated on 2024/04/18)

   Abstract:
   Treedepth is a well-studied graph invariant in the family of "width measures" that includes treewidth and pathwidth. Understanding these invariants in terms of excluded minors has been an active area of research. The recent Grid Minor Theorem of Chekuri and Chuzhoy [12] establishes that treewidth is polynomially approximated by the largest k ≤k grid minor. In this paper, we give a similar polynomial excluded-minor approximation for treedepth in terms of three basic obstructions: grids, tree, and paths. Specifically, we show that there is a constant c such that every graph of treedepth ≤ kc contains one of the following minors (each of treedepth ≤ k): ≤ the k ≤ k grid, ≤ the complete binary tree of height k, ≤ the path of order 2k. Let us point out that we cannot drop any of the above graphs for our purpose. Moreover, given a graph G we can, in randomized polynomial time, find either an embedding of one of these minors or conclude that treedepth of G is at most kc. This result has potential applications in a variety of settings where bounded treedepth plays a role. In addition to some graph structural applications, we describe a surprising application in circuit complexity and finite model theory from recent work of the second author [28].