# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### On Parameterized Independent Feedback Vertex Set

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Misra, N., Philip, G., Raman, V., & Saurabh, S. (2012). On Parameterized Independent
Feedback Vertex Set.* Theoretical Computer Science,* *461*,
65-75. doi:10.1016/j.tcs.2012.02.012.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-BE94-C

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