Computing treedepth in polynomial space and linear fpt time

Wojciech Nadara, Michał Pilipczuk, Marcin Smulewicz

The treedepth of a graph $G$ is the least possible depth of an elimination forest of $G$: a rooted forest on the same vertex set where every pair of vertices adjacent in $G$ is bou…