Approximation Algorithm For Minimum K-path Vertex Cover

Vertex cover is one of the most classic NP-hard problems in the field of combinatorial optimization.In 2011,Bresax et al.did some generalizations for this problem,and proposed k-path vertex cover problem(MVCPk).The k-path vertex cover problem is to find a minimum subset of vertices S(?)V such that every k-path in G contains at least one vertex from S.A connected k-path vertex cover(CVCPk)is a k-path vertex cover which induces a connected subgraph.When we consider the weighted version,in which vertices are given weights,the problem is to find a minimum weight k-path vertex cover(abbreviated MWVCPk).Liu et al presented a PTAS for the minimum CVCPk problem on unit disk graph.Zhang et al presented a PTAS for the minimum vertex cover problem on ball graph.For the MVCPk problem on ball graph,does it admit a PTAS?In this paper,We use a local search method to give a PTAS for VCPk on a ball graph for which the ratio between the maximum radius and the minimum radius has a constant upper bound.A PTAS is given for MCVCPk on unit disk graph which is much simper than the one in Liu's paper.In fact,there is no need of a constant approximation algorithm first.Furthermore,the algorithm and the theoretical analysis are also much simpler than that in Liu's paper.This thesis consists of five chapters.In Chapter 1,we introduce some basic nota-tions,give a brief survey on related works and state the main results obtained in this thesis.In Chapter 2,we present the approximation algorithm and theoretical analysis for MVCPk problem on ball graph.In Chapter 3,considering fault-tolerance,we generalize the MVCPk problem to the m-fold MVCPk problem and present a PTAS on ball graph.In Chapter 4,we present a simplified approximation algorithm and its theoretical analysis for CVCPk on unit disk graph.Chapter 5 is a conclusion of the thesis.