2026-08-15T02:07:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25149 2026-02-09T08:17:53Z ddc:004 open_access

Treedepth Inapproximability and Exponential ETH Lower Bound Bonnet, Édouard Neuen, Daniel Sokołowski, Marek treedepth lower bounds approximation 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²)} n-time exact algorithm and a polynomial-time O(OPT log^{3/2} 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 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(√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 > 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Daniel Neuen and Marek Sokołowski 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.17 urn:nbn:de:0030-drops-251494 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.17 eng https://creativecommons.org/licenses/by/4.0/legalcode