Skip to main content

A polynomial excluded-minor approximation of treedepth

Publication ,  Journal Article
Kawarabayashi, KI; Rossman, B
Published in: Journal of the European Mathematical Society
January 1, 2021

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.

Duke Scholars

Published In

Journal of the European Mathematical Society

DOI

ISSN

1435-9855

Publication Date

January 1, 2021

Volume

24

Issue

4

Start / End Page

1449 / 1470

Related Subject Headings

  • General Mathematics
  • 4904 Pure mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kawarabayashi, K. I., & Rossman, B. (2021). A polynomial excluded-minor approximation of treedepth. Journal of the European Mathematical Society, 24(4), 1449–1470. https://doi.org/10.4171/JEMS/1133
Kawarabayashi, K. I., and B. Rossman. “A polynomial excluded-minor approximation of treedepth.” Journal of the European Mathematical Society 24, no. 4 (January 1, 2021): 1449–70. https://doi.org/10.4171/JEMS/1133.
Kawarabayashi KI, Rossman B. A polynomial excluded-minor approximation of treedepth. Journal of the European Mathematical Society. 2021 Jan 1;24(4):1449–70.
Kawarabayashi, K. I., and B. Rossman. “A polynomial excluded-minor approximation of treedepth.” Journal of the European Mathematical Society, vol. 24, no. 4, Jan. 2021, pp. 1449–70. Scopus, doi:10.4171/JEMS/1133.
Kawarabayashi KI, Rossman B. A polynomial excluded-minor approximation of treedepth. Journal of the European Mathematical Society. 2021 Jan 1;24(4):1449–1470.

Published In

Journal of the European Mathematical Society

DOI

ISSN

1435-9855

Publication Date

January 1, 2021

Volume

24

Issue

4

Start / End Page

1449 / 1470

Related Subject Headings

  • General Mathematics
  • 4904 Pure mathematics
  • 0101 Pure Mathematics