PTAS for the minimum k-path connected vertex cover problem in unit disk graphs

In the Minimum k-Path Connected Vertex Cover Problem (MkPCVCP), we are given a connected graph G and an integer k ≥ 2, and are required to find a subset C of vertices with minimum cardinality such that each path with length k ? 1 has a vertex in C, and moreover, the induced subgraph GC] is connected. MkPCVCP is a generalization of the minimum connected vertex cover problem and has applications in many areas such as security communications in wireless sensor networks. MkPCVCP is proved to be NP-complete. In this paper, we give the first polynomial time approximation scheme (PTAS) for MkPCVCP in unit disk graphs, for every fixed k ≥ 2.