Treedepth Inapproximability and Exponential ETH Lower Bound

Abstract

Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a $2^{O(k^2)}n$-time exact algorithm and a polynomial-time $O(\text{OPT}{\log }^{3/2}\text{OPT})$-approximation algorithm, where the former algorithm returns an elimination forest of height $k$ (witnessing that treedepth is at most $k$) for the $n$-vertex input graph $G$, or correctly reports that $G$ has treedepth larger than $k$, and $\text{OPT}$ is the actual value of the treedepth. On the complexity side, exactly computing treedepth is NP-complete, but the known reductions do not rule out a polynomial-time approximation scheme (PTAS), and under the Exponential Time Hypothesis (ETH) only exclude a running time of $2^{o(\sqrt{n})}$ for exact algorithms. We show that 1.0003-approximating treedepth is NP-hard, and that exactly computing the treedepth of an $n$-vertex graph requires time $2^{\hat{I}\text{c◯}(n)}$, unless the ETH fails. We further derive that there exist absolute constants $\hat{I}´,c>0$ such that any $(1+\hat{I}´)$-approximation algorithm requires time $2^{\hat{I}\text{c◯}(n/{\log }^{c}n)}$. We do so via a simple direct reduction from Satisfiability to Treedepth, inspired by a reduction recently designed for Treewidth [STOC '25].

10 pages