The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer @math , to delete at most @math vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the @math -Colouring problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for @math -free graphs. We prove that it is NP-complete if @math contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for @math -free graphs. We show that it remains polynomial-time solvable for @math -free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most @math for a given integer @math . Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for @math -free graphs with the complexity of @math -Colouring, Independent Odd Cycle Transversal and other related problems.
We investigate a generalization of the classical Feedback Vertex Set (FVS) problem from the point of view of parameterized algorithms. 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 [email protected]?V(G), |F|@?k, such that G[V(G)@?F] is a forest and G[F] is an independent set; the parameter is k. Note that the similarly parameterized version of the FVS problem-where there is no restriction on the graph G[F]-has been extensively studied in the literature. The connected variant CFVS-where G[F] is required to be connected-has received some attention as well. 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 O(5^kn^O^(^1^)) time, where n is the number of vertices in the input graph G, and obtain a cubic (O(k^3)) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless [email protected]?NP Poly. We present a new deterministic algorithm for the Feedback Vertex Set problem parameterized by the solution size. Our algorithm runs in O^@?((2+@f)^k) time, where @f<1.619 is the golden ratio, surpassing the previously fastest O^@?((1+22)^k)-time deterministic algorithm due to (2010) [6]. In our development we follow the approach of ; however, thanks to a new reduction rule, we obtain not only better dependency on the parameter in the running time, but also a solution with simple analysis and only a single branching rule. In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.