Bounded Degree Group Steiner Tree Problems
share
We study two problems that seek a subtree T of a graph G=(V,E) such that T satisfies a certain property and has minimal maximum degree. - In the Min-Degree Group Steiner Tree problem we are given a collection S of groups (subsets of V) 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 at least k terminals. We show that if the former problem admits approximation ratio ρ then the later problem admits approximation ratio ρ· O(log k). For bounded treewidth graphs, we obtain approximation ratio O(log^3 n) for Min-Degree Group Steiner Tree. In the more general Bounded Degree Group Steiner Tree problem we are also given edge costs and degree bounds {b(v):v ∈ V}, and T should obey the degree constraints deg_T(v) ≤ b(v) for all v ∈ V. We give a bicriteria (O(log N log | S|),O(log^2 n))-approximation algorithm for this problem on tree inputs, where N is the size of the largest group, generalizing the approximation of Garg, Konjevod, and Ravi for the case without degree bounds.
READ FULL TEXT