Approximation Algorithms for the Covering Steiner Problem

The covering Steiner problem is a common generalization of the kappa-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative integer value (called the requirement) for each group, the problem is to find a minimum-weight tree spanning at least the required number of vertices of every group. When all requirements are equal to 1, this becomes the group Steiner problem, while if there is only one group which contains all vertices of the graph, the problem reduces to kappa-MST with kappa equal to the requirement of this unique group. We discuss two different linear relaxations of the problem for the case when the given graph is a tree and construct polylogarithmic approximation algorithms based on randomized LP rounding of these relaxations. An interesting feature of one of our LP rounding algorithms is that its approximation factor is much lower than the worst-case integrality gap of the LP relaxation. By using a probabilistic approximation of general metrics by tree metrics due to Bartal, our algorithms also apply to solve the covering Steiner problem on general graphs with a further polyogarithmic worsening in the approximation ratio.