Approximation Algorithm for the Minimum Connected k-Path Vertex Cover Problem

A vertex subset C of a connected graph G is called a connected k-path vertex cover (CV CPk) if every path of length k-1 contains at least one vertex from C, and the subgraph of G induced by C is connected. This concept has its background in the field of security and supervisory control. A variation, called CV CCk, asks every connected subgraph on k vertices contains at least one vertex from C. The MCV CPk (resp. MCV CCk) problem is to find a CV CPk (resp. CV CCk) with the minimum cardinality. In this paper, we give a k-approximation algorithm for MCV CPk under the assumption that the graph has girth at least k. Similar algorithm on MCV CCk also yields approximation ratio k, which is valid for any connected graph (without additional conditions).