Bounded Degree Group Steiner Tree Problems

Kortsarz, Guy; Nutov, Zeev

Motivated by some open problems posed in [13], we study three problems that seek a low degree subtree T of a graph [Formula: see text]. In the Min-Degree Group Steiner Tree problem we are given a collection of node subsets (groups), and T should contain a node from every group. In the Min-Degree Steiner k-Tree problem we are given a set R of terminals and an integer k, and T should contain k terminals. In both problems the goal is to minimize the maximum degree of T. In the more general Degrees Bounded Min-Cost Group Steiner Tree problem, we are also given edge costs and individual degree bounds [Formula: see text]. The output tree T should obey the degree constraints [Formula: see text] for all [Formula: see text], and among all such trees we seek one of minimum cost. When the input is a tree, an [Formula: see text] approximation for the cost is given in [10]. Our first result generalizes [10] – we give a bicriteria [Formula: see text]-approximation algorithm for Degrees Bounded Min-Cost Group Steiner Tree problem on tree inputs. This matches the cost ratio of [10] but also approximates the degrees within [Formula: see text]. Our second result shows that if Min-Degree Group Steiner Tree admits ratio [Formula: see text] then Min-Degree Steiner [Formula: see text]-Tree admits ratio [Formula: see text]. Combined with [12], this implies an [Formula: see text]-approximation for Min-Degree Steiner [Formula: see text]-Tree on general graphs, in quasi-polynomial time. Our third result is a polynomial time [Formula: see text]-approximation algorithm for Min-Degree Group Steiner Tree on bounded treewidth graphs.