Faster FPT Algorithm for 5-Path Vertex Cover

摘要

The problem of d-Path Vertex Cover, d-PVC lies in determining a subset F of vertices of a given graph G=(V,E) such that G F does not contain a path on d vertices. The paths we aim to cover need not to be induced. It is known that the d-PVC problem is NP-complete for any d = 2. When parameterized by the size of the solution k, 5-PVC has direct trivial algorithm with O(5^kn^{O(1)}) running time and, since d-PVC is a special case of d-Hitting Set, an algorithm running in O(4.0755^kn^{O(1)}) time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in O(4^kn^{O(1)}) time.