Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#362474] of Benjamin Rossman

Papers Published

  1. Kawarabayashi, KI; Rossman, B, A polynomial excluded-minor approximation of treedepth, Journal of the European Mathematical Society, vol. 24 no. 4 (January, 2021), pp. 1449-1470 [doi]
    (last updated on 2022/07/06)

    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×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 Ω(kc) has at least one of the following minors (each of treedepth at least k): • a k×k grid, • a complete binary tree of height k, or • a path of order 2k. 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(kc). 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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320