{"ID":2893048,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.13818","arxiv_id":"2507.13818","title":"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^{Ω(n)}$, unless the ETH fails. We further derive that there exist absolute constants $δ, c \u003e 0$ such that any $(1+δ)$-approximation algorithm requires time $2^{Ω(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].","short_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 for...","url_abs":"https://arxiv.org/abs/2507.13818","url_pdf":"https://arxiv.org/pdf/2507.13818v1","authors":"[\"Édouard Bonnet\",\"Daniel Neuen\",\"Marek Sokołowski\"]","published":"2025-07-18T11:06:13Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}