Spanheight, A Natural Extension of Bandwidth and Treedepth

Abstract

In graph theory, the treedepth problem finds depth first search spanning trees of bounded height and is NP-Complete. We study an extension of treedepth where we bound the distance between adjacent vertices in the depth first search spanning tree. This graph problem has a close resemblance to bandwidth and treespan. We call this problem spanheight and show that its NP-Complete. We introduce a single exponential algorithm using O(n^2 9^n) time and O(n^2 2^n) space. We look at meta-theorems for proving membership in FPT, and present an O(n t^4 2^(7t^3 2^t log(t)) ) time and O(n 2^(3t^3 2^t log(t))) space FPT algorithm by parameterizing with treedepth.