Approximation Algorithm For The Minimum Weight Connected K-Subgraph Cover Problem

A subset F of vertices is called a connected k-subgraph cover(V CCk) if every connected subgraph on k vertices contains at least one vertex from F. The minimum weight connected k-subgraph cover problem(M W V CCk) is that: Given a graph G =(V, E) and a vertex-weight function w, the goal is to ?nd a minimum weight vertex set F ? V such that every connected subgraph on k vertices has at least one vertex from F. M W V CCkhas its background in the ?eld 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(M W V CPk) 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.In this paper, we ?rstly propose the new model called minimum weight connected k-subgraph cover, and study approximation algorithm in a general graph. Assuming that the grith of the graph is at least k, we reduce the approximation ratio to k- 1,which is tight for our algorithm. For k = 2. M W V CC2 is exactly the minimum weight vertex cover problem. For k = 3, since M W V CC3 is the same as M W V CP3 and the girth of a simple graph is always at least three, Tu and Zhou’s result [30] is included in our result. Secondly, we present approximation algorithms for the M W V CCkproblem in cubic graph for general k, especially, for k = 3, 4, 5, tight examples are given showing the sharpness of our approximation ratios. Last but not least, we conclude the thesis by discussing some potential improvements.