# A Faster Parameterized Algorithm for Treedepth

arXiv: https://arxiv.org/abs/1401.7540 · HTML: https://mlsanity.com/paper/1401.7540/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2014.

## Built on by (most cited first, 2 of 2)

- [A Structural Complexity Analysis of Synchronous Dynamical Systems](https://mlsanity.com/paper/2312.08385/) (2023)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)

## Abstract (arXiv)

The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which---given as input an n-vertex graph, a tree decomposition of the graph of width w, and an integer t---decides Treedepth, i.e. whether the treedepth of the graph is at most t, in time 2O(wt) · n. If necessary, a witness structure for the treedepth can be constructed in the same running time. In conjunction with previous results we provide a simple algorithm and a fast algorithm which decide treedepth in time 2^2O(t) · n and 2O(t2) · n, respectively, which do not require a tree decomposition as part of their input. The former answers an open question posed by Ossona de Mendez and Nesetril as to whether deciding Treedepth admits an algorithm with a linear running time (for every fixed t) that does not rely on Courcelle's Theorem or other heavy machinery. For chordal graphs we can prove a running time of 2O(t log t)· n for the same algorithm.