Item

Abstract

We investigate a generalization of the classical \textscFeedback Vertex Set} (FVS) problem from the point of view of parameterized algorithms. \textsc{Independent Feedback Vertex Set} (IFVS) is the ``independent'' variant of the FVS problem and is defined as follows: given a graph \(G\) and an integer \(k\), decide whether there exists \(F\subseteq V(G)\), \(|F| ≤q k\), such that \(G[V(G) \setminus F]\) is a forest and \(G[F]\) is an independent set; the parameter is \(k\). Note that the similarly parameterized versions of the FVS problem --- where there is no restriction on the graph \(G[F]\) --- and its connected variant CFVS --- where \(G[F]\) is required to be connected --- have been extensively studied in the literature. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in time \(O(5^kn^{O(1))\) time where \(n\) is the number of vertices in the input graph \(G\), and obtain a cubic (\(O(k³)\)) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless \(CoNP \subseteq NP/Poly\).