An improved parameterized algorithm for the independent feedback vertex set problem

In this paper, we develop a new parameterized algorithm for the Independent Feedback Vertex Set problem. Given a graph G=(V,E)G=(V,E), the goal of the problem is to determine whether there exists a vertex subset F⊆VF⊆V such that V−FV−F induces a forest in G and F is an independent set. We show that there exists a parameterized algorithm that can determine whether a graph contains an IFVS of size k   or not in time O(4kn2)O(4kn2). To our best knowledge, this result improves the known upper bound for this problem, which is O(5knO(1))O(5knO(1)).