A faster FPT algorithm for 3-path vertex cover

摘要

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 psi(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 psi(k)(G). In this paper we present an FPT algorithm to the 3-PVCP with runtime O(1.8172(s)n(O(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 (2(s)n(O(1))) upper bound by Tu [5] and O(1.882(s)n(O(1))) upper bound by Wu [13]. (C) 2015 Elsevier B.V. All rights reserved.