Treedepth Inapproximability and Exponential ETH Lower Bound
Édouard Bonnet, Daniel Neuen, Marek Sokołowski · 2025
Read Treedepth Inapproximability and Exponential ETH Lower Bound by Édouard Bonnet, Daniel Neuen, Marek Sokołowski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13818.txt.
Introduction
Édouard Bonnet, Daniel Neuen, and Marek Sokołowski settle a hardness question in a 2025 computer science paper. Treedepth grades how deeply a network must be peeled apart layer by layer. Fast exact tools for it are slow in the worst case. A rough but quick estimate tool also existed.
The team proves that even a very close estimate is hard to compute. Exact answers need time that grows at a steep rate with network size. That claim rests on a widely believed guess about hard problems. Near exact estimates face almost the same barrier, they show. The proof adapts a fresh reduction built for a sister measure called treewidth. The results close the door on a fast estimation scheme for treedepth.
Catalog record
| CREATOR | Édouard Bonnet, Daniel Neuen, Marek Sokołowski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13818
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Treedepth Inapproximability and Exponential ETH Lower Bound Édouard Bonnet, Daniel Neuen, Marek Sokołowski 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 2^{O(k^{2})}n -time exact algorithm and a polynomial-time O ( OPT log 3 / 2 OPT ) O(\text{OPT}\log^{3/2}\text{OPT}) -approximation algorithm, where the former algorithm returns an elimination forest of height k k (witnessing that treedepth is at most k k ) for the n n -vertex input graph G G , or correctly reports that G G has treedepth larger than k 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 ) 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 n -vertex graph requires time 2 Ω ( n ) 2^{\Omega(n)} , unless the ETH fails. We further derive that there exist absolute constants δ , c > 0 \delta,c>0 such that any ( 1 + δ ) (1+\delta) -approximation algorithm requires time 2 Ω ( n / log c n ) 2^{\Omega(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]. 1 Introduction The treedepth \td(G) of a graph G is the least integer k such that there is a rooted forest F of height k with same vertex set as G such that every edge of G is between two nodes in ancestor–descendant relationship in F . Treedepth and treewidth, \tw , are related by the inequalities \tw(G)+1\leqslant\td(G)\leqslant\tw(G)\cdot(1+\log n) , for every n -vertex graph G . An n -vertex path has treewidth (even pathwidth) 1, but treedepth \Theta(\log n) . Treedepth comes into play in various contexts. Notably, in the sparsity theory initiated by Nešetřil and Ossona de Mendez [ 26 ] , treedepth provides a characterization of classes of bounded expansion (roughly speaking, classes excluding, as subgraphs, short subdivisions of graphs of large average degree). Graph classes with bounded expansion are exactly those with so-called low treedepth covers (some form of cover by graphs of bounded treedepth) [ 21 ] . Graphs of bounded treewidth famously lend themselves to fixed-parameter tractable (FPT) algorithms for various NP -hard problems, with parameter the width of the computed (or given) tree-decompositions, by performing dynamic programming over these decompositions (see, e.g., [ 7 , Chapter 7] ). However, this method consumes essentially as much space as it takes time; in particular, most of these algorithms for NP -hard problems take exponential space in the treewidth. Bounded treedepth, in contrast, often allows for parameterized algorithms with comparable running time but using only polynomial space; see for instance [ 12 , 20 , 22 , 23 ] . Other uses of treedepth can be found in formula complexity [ 18 ] , distributed model checking [ 10 ] , product structure theory [ 9 ] , relation to polynomial minors [ 16 , 14 ] , graph circumference [ 6 ] etc. We now survey the current state of the art on computing and approximating the treedepth of an input graph—the topic of the current paper. Note that Treedepth was the selected problem for the 2020 edition of the PACE challenge [ 17 ] . The decision version of Treedepth is NP -complete [ 24 , 3 ] . There is an easy algorithm that computes the treedepth of an n -vertex graph in time O(2^{n}\cdot n) , and a slightly faster exponential algorithm computing the decomposition in time O(1.9602^{n}) [ 11 ] . An FPT (exact) algorithm in 2^{O(k^{2})}n time has been established, first needing exponential space [ 25 ] , and later improved to only use polynomial space [ 19 ] . More precisely, these algorithms run in time 2^{O(\td(G)\tw(G))}n on an n -vertex graph G . An outstanding open question is whether running time 2^{O(k)}n^{O(1)} can be obtained. Notably, Treewidth admits constant-approximation algorithms in this running time. In contrast to treewidth, such a result remains elusive for Treedepth . On the front of polynomial-time approximation algorithms, the best factor that currently can be achieved is O(\tw(G)\log^{3/2}\tw(G)) [ 8 ] , hence O(\td(G)\log^{3/2}\td(G)) . The previously known hardness results [ 24 , 3 ] are rather unsatisfactory: First of all, they did not rule out a polynomial-time approximation scheme (PTAS) for Treedepth . Furthermore, by following the reductions presented in both papers, we can only infer a 2^{\Omega(\sqrt{n})} lower bound for the exact variant of the problem under the Exponential Time Hypothesis (ETH). 1 1 1 The assumption that there is some \lambda>1 such that n -variable 3-SAT requires time \Omega(\lambda^{n}) . Naturally, this excludes any 2^{o(\sqrt{k})}n^{O(1)} -time parameterized exact algorithm for the problem under ETH. Our Results. In this work, we design a simple linear reduction from Satisfiability to Treedepth . It draws inspiration from a recent similar result for Treewidth [ 4 ] , and also relies on the hardness of Vertex Cover (i.e., the task of finding a smallest vertex subset hitting every edge) on tripartite graphs. Our reduction yields the following inapproximability results and computational lower bounds for Treedepth . Theorem 1.1 . It is NP -hard to 1.0003-approximate Treedepth . In particular, the theorem rules out a polynomial-time approximation scheme (PTAS) for Treedepth (assuming \textsf{P}\neq\textsf{NP} ). Theorem 1.2 . Assuming ETH, there is some \varepsilon>0 such that the treedepth of an n -vertex graph cannot be computed in time O(2^{\varepsilon n}) . This also excludes 2^{o(k)}n^{O(1)} -time parameterized exact algorithms for the problem under ETH. In fact, we obtain that even approximating treedepth to a small constant factor requires almost exponential time. Theorem 1.3 . Assuming ETH, there exist absolute constants \delta,\varepsilon,c>0 such that (1+\delta) -approximating the treedepth of an n -vertex graph cannot be done in time O(2^{\varepsilon n/\log^{c}n}) . 2 Preliminaries In this work, we consider only simple undirected graphs with no self-loops. For a graph G , we define V(G) to be the set of vertices, E(G) to be the set of edges, and \text{cc}(G) to be the set of connected components of G . Also, we write N_{G}(v) for the set of neighbors of a vertex v\in V(G) in the graph G . A forest F is a graph without cycles; it is rooted if each connected component of F (a tree ) has a root . The depth of a forest is then the number of vertices on the longest root-to-leaf path in F . A vertex u is an ancestor of v in F if u lies on the path between v and the root of the tree of F containing v ; we equivalently then say that v is a descendant of u . In particular, every vertex is its own ancestor and descendant. A set S\subseteq V(G) is a vertex cover if each edge of G is incident