Abstract

Given a graph G and degree bound B on its nodes, the bounded-degree minimum spanning tree (BDMST) problem is to find a minimum cost spanning tree among the spanning trees with maximum degree B. This bi-criteria optimization problem generalizes several combinatorial problems, including the Traveling Salesman Path Problem (TSPP). An (α, f(B))-approximation algorithm for the BDMST problem produces a spanning tree that has maximum degree f(B) and cost within a factor α of the optimal cost. K¨one mann and Ravi [13,14] give a polynomial time (1 + 1 β, bB(1 + β) + log b n)-approximation algorithm for any b>1, β>0. In a recent paper [2], Chaudhuri et al. improved these results with a (1, bB+√blogb n)-approximation for any b>1. In this paper, we present a (1+1 β , 2B(1+β)+o(B(1+β)))-approximation polynomial-time algorithm. That is, we give the first algorithm that approximates both degree and cost to within a constant factor of the optimal. These results generalize to the case of non-uniform degree bounds. The crux of our solution is an approximation algorithm for the related problem of finding a minimum spanning tree (MST) in which the maximum degree of the nodes is minimized, a problem we call the minimum degree MST (MDMST) problem. Given a graph G for which the degree of the MDMST solution is Δopt, our algorithm obtains in polynomial time an MST of G of degree at most 2Δopt + o(Δopt). This result improves on a previous result of Fischer [4] that finds an MST of G of degree at most bΔopt + log b n for any b>1, and on the improved quasipolynomial algorithm of [2]. Our algorithm uses the push-relabel framework developed by Goldberg [7] for the maximum flow problem. To our knowledge, this is the first instance of a push-relabel approximation algorithm for an NP-hard problem, and we believe these techniques may have larger impact. We note that for B = 2, our algorithm gives a tree of cost within a (1 + )factor of the optimal solution to TSPP and of maximum degree O(1 ) for any >0, even on graphs not satisfying the triangle inequality.