A faster FPT algorithm for 3-path vertex cover

• The k-path vertex cover problem (k-PVCP) is to find a minimum set of vertices that meets every path of order k in G.
• The k  -PVCP problem is NP-hard for any integer k≥2k≥2.
• We present a FPT algorithm with runtime O⁎(1.8127s)O⁎(1.8127s) for the 3-PVCP problem, where s is a size of an optimal solution.

The k-path vertex cover of a graph G is a subset S of vertices of G such that every path on k vertices in G contains at least one vertex from S  . Denote by ψk(G)ψk(G) the minimum cardinality of a k-path vertex cover set in G. The minimum k-path vertex cover problem (k-PVCP) is to find a k  -path vertex cover of size ψk(G)ψk(G). In this paper we present an FPT algorithm to the 3-PVCP with runtime O(1.8172snO(1))O(1.8172snO(1)) on a graph with n vertices. The algorithm constructs a 3-path vertex cover of size at most s in a given graph G, or reports that no such 3-path vertex cover exists in G  . This improves previous O(2snO(1))O(2snO(1)) upper bound by Tu [5] and O(1.882snO(1))O(1.882snO(1)) upper bound by Wu [13].