Approximation algorithm for the minimum weight connected k-subgraph cover problem

• We propose the minimum weight connected k  -subgraph cover problem (MWVCCkMWVCCk).
• We give a (k−1k−1)-approximation for MWVCCkMWVCCk when the girth is at least k.
• An example is given showing that the analysis of our algorithm is tight.

A subset F of vertices is called a connected k  -subgraph cover (VCCkVCCk) if every connected subgraph on k vertices contains at least one vertex from F. The minimum weight connected k  -subgraph cover problem (MWVCCkMWVCCk) has its background in the field of security and supervisory control. It is a generalization of the minimum weight vertex cover problem, and is related with the minimum weight k  -path cover problem (MWVCPkMWVCPk) which requires that every path on k vertices has at least one vertex from F. A k-approximation algorithm can be easily obtained by LP rounding method. Assuming that the girth of the graph is at least k  , we reduce the approximation ratio to k−1k−1, which is tight for our algorithm.