Subset Feedback Vertex Set is fixed parameter tractable
Venue
ICALP 2011 (to appear)
Publication Year
2011
Authors
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
BibTeX
Abstract
In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (SFVS in short) where an instance comes additionally with a set S of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis SFVS was studied from the approximation algorithms perspective by Even et al. [SICOMP'00, SIDMA'00].
The question whether the SFVS problem is fixed parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parametrized by |S|. Next we present an algorithm which reduces the size of S to O(k^3) in 2^{O(k\log k)}n^{O(1)} time using kernelization techniques such as the 2-Expansion Lemma, Menger's theorem and Gallai's theorem. These two facts allow us to give a 2^{O(k\log k)} n^{O(1)} time algorithm solving the SFVS problem, proving that it is indeed fixed parameter tractable.
