A Randomized Polynomial Kernel for Subset Feedback Vertex Set
Eva-Maria C. Hols, Stefan Kratsch · Theory of Computing Systems · 2017
The subset feedback vertex set problem generalizes the classical feedback vertex set problem and asks, for a given undirected graph G = (V, E), a set S ⊆ V, and an integer k, whether there exists a set X of at most k vertices such that no cycle in G − X contains a vertex of S. It was independently shown by Cygan et al. (ICALP ’11, SIDMA ’13) and Kawarabayashi and Kobayashi (JCTB ’12) that subset feedback vertex set is fixed-parameter tractable for parameter k. Cygan et al. asked whether the problem also admits a polynomial kernelization. We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization for the equivalent version where S is a set of edges. In a first step we show that edge subset feedback vertex set has a randomized polynomial kernel parameterized by |S| + k with $\mathcal {O}(|S|^{2}k)$ vertices. For this we use the matroid-based tools of Kratsch and Wahlström (FOCS ’12) that for example were used to obtain a polynomial kernel for s-multiway cut. Next we present a preprocessing that reduces the given instance (G, S, k) to an equivalent instance (G′, S′, k′) where the size of S′ is bounded by $\mathcal {O}(k^{4})$ . These two results lead to a randomized polynomial kernel for subset feedback vertex set with $\mathcal {O}(k^{9})$ vertices.