Title: Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Abstract: 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 \subseteq 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 $|S|$. 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.