A fixed-parameter algorithm for the vertex cover P3 problem

A subset F of vertices of a graph G is called a vertex cover P-t set if every path of order t in G contains at least one vertex from F. Denote by psi t(G) the minimum cardinality of a vertex cover P-t set in G. The vertex cover P-t (VCPt) problem is to find a minimum vertex cover P-t 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(2(k)k(3.376) + n(4)m) 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 P-3 set searched for. (C) 2014 Elsevier B.V. All rights reserved.