# 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.