Before revision: This work considers the following extension of the tree-depth problem : for a given input graph G and integers k and b, find a rooted forest F of height at most k and width at most b (defined as the maximum number of vertices allowed in a level of F) such that G is a subgraph of the closure of F . We are interested in the case when G is a line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive b-approximation algorithm.
After revision: The tree-depth problem : for a given input graph G and integers k and b, find a rooted forest F of height at most k and width at most b (defined as the maximum number of vertices allowed in a level of F) such that G is a subgraph of the closure of F . We are interested in the case when G is a line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive b-approximation algorithm.