  The tree-depth problem can be seen as finding an elimination tree of minimum
height for a given input graph $G$. We introduce a bicriteria generalization in
which additionally the width of the elimination tree needs to be bounded by
some input integer $b$. We are interested in the case when $G$ is the line
graph of a tree, proving that the problem is NP-hard and obtaining a
polynomial-time additive $2b$-approximation algorithm. This particular class of
graphs received significant attention in the past, mainly due to a number of
potential applications, e.g. in parallel assembly of modular products, or
parallel query processing in relational databases, as well as purely
combinatorial applications, including searching in tree-like partial orders
(which in turn generalizes binary search on sorted data).
