Approximation algorithm for minimum weight connected-k-subgraph cover

Abstract For a given graph G, the minimum weight connected-k-subgraph cover problem (MinWCkSC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C. Previously, Zhang et al. [37] presented a ( k − 1 ) -approximation algorithm for MinWCkSC under the assumption that the girth of G, which is the length of a shortest cycle of G, is at least k. In this paper, we improve this result by showing that ( k − 1 ) -approximation can be achieved when the girth requirement is relaxed from k to 2 k / 3 .