Fixed-parameter algorithms for vertex cover P3

Let Pℓ denote a path in a graph G=(V,E) with ℓ vertices. A vertex cover Pℓ set C in G is a vertex subset such that every Pℓ in G has at least a vertex in C. The Vertex CoverPℓ problem is to find a vertex cover Pℓ set of minimum cardinality in a given graph. This problem is NP-hard for any integer ℓ⩾2. The parameterized version of Vertex CoverPℓ problem called k-Vertex CoverPℓ asks whether there exists a vertex cover Pℓ set of size at most k in the input graph. In this paper, we give two fixed parameter algorithms to solve the k-Vertex CoverP3 problem. The first algorithm runs in time O∗(1.7964k) in polynomial space and the second algorithm runs in time O∗(1.7485k) in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.