Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

Abstract

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = ( V, E ) with a degree upper bound B v on each vertex v ∈ V , and the task is to find a spanning tree of minimum cost that satisfies all the degree bounds. Let OPT be the cost of an optimal solution to this problem. In this article we present a polynomial-time algorithm which returns a spanning tree T of cost at most OPT and d T ( v ) ≤ B v + 1 for all v , where d T ( v ) denotes the degree of v in T . This generalizes a result of Fürer and Raghavachari [1994] to weighted graphs, and settles a conjecture of Goemans [2006] affirmatively. The algorithm generalizes when each vertex v has a degree lower bound A v and a degree upper bound B v , and returns a spanning tree with cost at most OPT and A v - 1 ≤ d T ( v ) ≤ B v + 1 for all v ∈ V . This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [2001] for the design of approximation algorithms.