Approximation algorithms for minimum (weight) connected kk-path vertex cover

A vertex subset CC of a connected graph GG is called a connected kk-path vertex cover (CVCPkCVCPk) if every path on kk vertices contains at least one vertex from CC, and the subgraph of GG induced by CC is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) CVCPkCVCPk problem. We first show that the minimum weight CVCPkCVCPk problem can be solved in time O(n)O(n) when the graph is a tree, and can be solved in time O(rn)O(rn) when the graph is a uni-cyclic graph whose unique cycle has length rr, where nn is the number of vertices. Making use of the algorithm on trees, we present a kk-approximation algorithm for the minimum (cardinality) CVCPkCVCPk problem under the assumption that the graph has girth at least kk. An example is given showing that performance ratio kk is asymptotically tight for our algorithm.