A fixed-parameter algorithm for the vertex cover P3 problem

A subset F of vertices of a graph G is called a vertex cover Pt set if every path of order t in G contains at least one vertex from F. Denote by ψt(G) the minimum cardinality of a vertex cover Pt set in G. The vertex cover Pt (VCPt) problem is to find a minimum vertex cover Pt set. The VCPt problem is NP-hard for any integer t≥2. In this paper, we restrict our attention to the VCP3 problem and present a fixed-parameter algorithm with runtime O(2kk3.376+n4m) for the VCP3 problem. Here, n denotes the number of vertices, m denotes the number of the edges, k denotes the size of the vertex cover P3 set searched for.