An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion

摘要

The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied Feedback Vertex Set (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196-207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7~kn~(O(1)) In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65~kn~(O(1)), thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251-260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomasse (ACM Trans. Algorithms 6(2), 2010).