Dekel Tsur

In the 4-PATH VERTEX COVER problem, the input is an undirected graph G and an integer k. The goal is to decide whether there is a set S of vertices of size at most k such that every path with 4 vertices in G contains at least one vertex of S. In this paper we give a parameterized algorithm for 4-PATH VERTEX COVER whose time complexity is 2.619^k⋅n^O(1), where n denotes the number of vertices of the input graph.