On the weighted kk-path vertex cover problem

A subset SS of vertices of a graph GG is called a kk-path vertex cover   if every path of order kk in GG contains at least one vertex from SS. The cardinality of a minimum kk-path vertex cover is called the kk-path vertex cover number   of a graph GG, denoted by ψk(G)ψk(G). It is known that the minimum kk-path vertex cover problem (kk-PVCP) is NP-hard for all k≥2k≥2. In this paper we consider the weighted version of a kk-PVCP (kk-WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in GG such that the graph obtained by deleting this set from GG has no PkPk. This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the kk-WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the kk-path vertex cover number of a tree with time complexity O(k⋅|V(G)|)O(k⋅|V(G)|) is presented.