Approximation algorithm for minimum weight connected-k-subgraph cover

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.

Authors

• Pengcheng Liu
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Xiaohui Huang

Keywords

• Connected-k-subgraph cover
• Approximation algorithm
• Girth