# Computing treedepth in polynomial space and linear fpt time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2022.

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

- [A Structural Complexity Analysis of Synchronous Dynamical Systems](https://mlsanity.com/paper/2312.08385/) (2023)

## Abstract (arXiv)

The treedepth of a graph G is the least possible depth of an elimination forest of G: a rooted forest on the same vertex set where every pair of vertices adjacent in G is bound by the ancestor/descendant relation. We propose an algorithm that given a graph G and an integer d, either finds an elimination forest of G of depth at most d or concludes that no such forest exists; thus the algorithm decides whether the treedepth of G is at most d. The running time is 2O(d2)· nO(1) and the space usage is polynomial in n. Further, by allowing randomization, the time and space complexities can be improved to 2O(d2)· n and dO(1)· n, respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity 2O(d2)· n, but uses exponential space.