Minimum k-path vertex cover

AbstractA subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ψk(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining ψk(G) is NP-hard for each k≥2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ψk(G) and provide several estimations and exact values of ψk(G). We also prove that ψ3(G)≤(2n+m)/6, for every graph G with n vertices and m edges