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