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

作者：Cygan Marek; Pilipczuk Marcin; Pilipczuk Michal; Wojtaszczyk Jakub Onufry

来源：Algorithmica, 2012, 64(1): 170-188.

DOI：10.1007/s00453-011-9578-2

• Fixed parameter tractability
• Kernelization
• Pathwidth
• Caterpillar graph

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 (k) n (O(1)). In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65 (k) n (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 Thomass, (ACM Trans. Algorithms 6(2), 2010).

• 出版日期2012-9