SUBSET FEEDBACK VERTEX SET IS FIXED-PARAMETER TRACTABLE

The classical FEEDBACK VERTEX SET problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. FEEDBACK VERTEX SET has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named SUBSET FEEDBACK VERTEX SET (SUBSET-FVS), where an instance comes additionally with a set S subset of V 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, SUBSET-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225-267; SIAM J. Comput., 30 (2000), pp. 1231-1252]. The question of whether the SUBSET-FVS 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 parameterized by vertical bar S vertical bar. Next we present an algorithm which reduces the given instance to 2(k)n(O(1)) instances with the size of S bounded by O(k(3)), 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 SUBSET-FVS problem, proving that it is indeed fixed-parameter tractable.