A constant-factor approximation algorithm for the k-MST problem

Given an undirected graph with nonnegative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This p roblem is known to be NP-hard. We present a simple approximation algorithm that finds a solution whose cost is less than 17 times the cost of the opti mum. This improves upon previous performance ratios for this problem - O(ro ot k) due to Ravi et al., O(log(2) k) due to Awerbuch et al, and the previo us best bound of O(log k) due to Rajagopalan and Vazirani. Given any 0 < a < 1, we first present a bicriteria approximation algorithm that outputs a t ree on p greater than or equal to ak vertices of total cost at most 2pL/(1- a) k, where L is the cost of the optimal k-MST. The running time of the alg orithm is O(n(2) log(2) n) on an n-node graph. We then show how to use this algorithm to derive a constant factor approximation algorithm for the k-MS T problem. The main subroutine in our algorithm is an approximation algorit hm of Goemans and Williamson for the prize-collecting Steiner tree problem. (C) 1999 Academic Press.