An Improved FPT Algorithm for Independent Feedback Vertex Set

We study the Independent Feedback Vertex Set problem—a variant of the classic Feedback Vertex Set problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set \(S\subseteq V(G)\) such that \(G{\setminus }S\) is a forest and S is an independent set of size at most k. We present an \(\mathcal {O}^*((1+\varphi ^{2})^{k})\)-time FPT algorithm for this problem, where \(\varphi <1.619\) is the golden ratio, improving the previous fastest \(\mathcal {O}^*(4.1481^{k})\)-time algorithm given by Agrawal et al. [1]. The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic Feedback Vertex Set problem.