Treedepth Inapproximability and Exponential ETH Lower Bound

Édouard Bonnet, Daniel Neuen, Marek Sokołowski

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 algorith…