Subset feedback vertex set is fixed parameter tractable

Authors:
Preprint
Publisher website
Google Scholar
Abstract
The FEEDBACK VERTEX SET problem, given an undirected graph G and an integer k, asks whether there exists a set of at most k vertices that hits all cycles in the graph G. FEEDBACK VERTEX SET was intensively studied from the parameterized perspective. In this paper we consider the SUBSET FEEDBACK VERTEX SET problem, where an instance comes additionally with a subset of vertices S and we ask for a set of at most k vertices that hits all simple cycles passing through S. The parameterized complexity of SUBSET FEEDBACK VERTEX SET was posted as an open problem by S. Saurabh in 2009. We begin by showing that this problem is FPT when parameterized by |S|. Moreover, we present an algorithm which reduces the size of |S| to O(k^3) using kernelization techniques such as the 2-Expansion Lemma, Menger's theorem and Gallai's theorem. These two results prove that the SUBSET FEEDBACK VERTEX SET problem is FPT when parameterized by k and the time complexity of our algorithm is 2^O(k log k) n^O(1). Furthermore, we present a connection between the SUBSET FEEDBACK VERTEX SET problem and terminal separation problems such as MULTIWAY CUT and MULTICUT. We show that SUBSET FEEDBACK VERTEX SET is a generalisation of MULTIWAY CUT and with an additional constraint SUBSET FEEDBACK VERTEX SET becomes as hard as MULTICUT. It is known that MULTIWAY CUT is FPT when parameterized by the solution size k but for MULTICUT the existence of such a FPT algorithm is a major and long-standing open problem in the FPT field. Our results imply that in some sense SUBSET FVS falls between MULTIWAY CUT and MULTICUT. Since SUBSET-FVS is at least as hard as NODE MULTIWAY CUT and it is still FPT, we make a step towards solving the MULTICUT problem.

This publication has 8 references indexed in Scilit: