Approximating the spanning k-tree forest problem

Abstract

The spanning star forest problem is an interesting algorithmic problem in combinatorial optimization and finds different applications. We generalize it into the spanning k-tree forest problem, which is to find a maximum spanning forest in which each tree component has a central vertex and other vertices in the component have distance at most k away from the central vertex. We show that this new problem can be approximated with ratio $1 - \frac{1}{k+1}$ in polynomial time for both undirected and directed graphs. In the weighted distance model, a -approximation algorithm is presented for it. © 2012 World Scientific Publishing Company.