A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network

Because of its application in the field of security in wireless sensor networks, k-path vertex cover ((hbox {VCP}_k)) has received a lot of attention in recent years. Given a graph (G=(V,E)), a vertex set (Csubseteq V) is a k-path vertex cover ((hbox {VCP}_k)) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G ((hbox {CVCP}_k)) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for (hbox {MinCVCP}_k) on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.