hide
Free keywords:
-
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\).
