The Complexity of Bicriteria Tree-Depth

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. This particular class of graphs received a significant attention in the past, mainly due to a number of potential applications it provides. These include applications in parallel processing, e.g., 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). The latter can be used for automated program testing.