An FPT algorithm for the vertex cover P4 problem
A subset F of vertices of a graph G is called a vertex cover P t ( V C P t ) set if every path of order t in G contains at least one vertex from F . The vertex cover P t ( V C P t ) problem is to find a minimum V C P t set in a graph. The V C P t problem is NP-complete for any integer t ≥ 2 . In this paper, we restrict our attention to the V C P 4 problem and present an FPT algorithm with runtime O ∗ ( 3 k ) for the V C P 4 problem. The algorithm constructs a V C P 4 set of size at most k in a given graph G , or reports that no such V C P 4 set exists in G .