Approximation algorithms for the K- MST problem

Abstract

Given a graph GGG on nnn vertices, the kkk-MST optimization problem is to find a tree spanning at least kkk vertices of GGG such that the cost of the tree is minimized over all such possible trees. The main contribution of this thesis is a clear description of Garg’s [10] 5 and 3-approximation algorithms for the problem. We also give clean proofs for the performance guarantees of both these algorithms. We also provide some insights into the working of these algorithms. In particular, we show that contrary to intuition, the sizes of both the pruned as well as the un-pruned tree can decrease with increase in potential. Prior to describing Garg’s algorithm in detail, we also describe the O(y/k)O(y/k)O(y/k), O(log?k)O(\log^k)O(logk), seventeen and 5-approximation algorithms for the problem. We also give a new simpler proof showing that the 2-approximation guarantee given by Goemans-Williamson’s algorithm for the prize-collecting Steiner tree problem is not tight. We also make an observation that an ?\alpha?-approximation algorithm for the general kkk-MST problem gives an (?\alpha?-M)-approximation algorithm for the ‘rooted’ version of the problem.