A Constant-Factor Approximation Algorithm for the k-MST Problem

Given an undirected graph with nonnegative edge costs and an integerk, the k-MST problem is that of finding a tree of minimum cost on k nodes. This problem 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 optimum. This improves upon previous performance ratios for this problem −O(√k) due to Raviet al.,O(log² k) due to Awerbuchet al., and the previous best bound of O(log k) due to Rajagopalan and Vazirani. Given any 0<α<1, we first present a bicriteria approximation algorithm that outputs a tree on p≥αk vertices of total cost at most 2pL/(1−α) k, where L is the cost of the optimal k-MST. The running time of the algorithm is O(n²log² n) on an n-node graph. We then show how to use this algorithm to derive a constant factor approximation algorithm for the k-MST problem. The main subroutine in our algorithm is an approximation algorithm of Goemans and Williamson for the prize-collecting Steiner tree problem.