An FPT algorithm for the vertex cover P4P4 problem

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