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.
Another way to obtain tractability results is to restrict the input to special graph classes in order to determine graph properties that make the problem polynomial-time solvable. We already mentioned some classes for which Independent Feedback Vertex Set is -complete. In a companion paper @cite_37 , we show that the problem is polynomial-time solvable for graphs of diameter @math , and as stated above, the problem is -complete on graphs of diameter @math . Tamura et al. @cite_31 showed that Independent Feedback Vertex Set is polynomial-time solvable for chordal graphs, graphs of bounded treewidth and for cographs. The latter graphs are also known as @math -free graphs ( @math denotes the path on @math vertices and a graph is @math -free if it has no induced subgraph isomorphic to @math ), and this strengthened a result of Brandst "adt et al. @cite_26 , who proved that Near-Bipartiteness is polynomial-time solvable for @math -free graphs.
@cite_37 @cite_26 @cite_31
2741305621 2057355493 1491760138
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets @math and @math , where @math is an independent set and @math induces a forest. The set @math in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2. A cycle transversal (or feedback vertex set) of a graph G is a subset T@?V(G) such that T@?V(C) 0@? for every cycle C of G. This work considers the problem of finding special cycle transversals in perfect graphs and cographs. We prove that finding a minimum cycle transversal T in a perfect graph G is NP-hard, even for bipartite graphs with maximum degree four. Since G-T is acyclic, this result implies that finding a maximum acyclic induced subgraph of a perfect graph is also NP-hard. Other special properties of T are considered. A clique (stable, respectively) cycle transversal, or simply cct (sct, respectively) is a cycle transversal which is a clique (stable set, respectively). Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known, even for perfect graphs. We characterize cographs with cct in terms of forbidden induced subgraphs and describe their structure. This leads to linear time recognition of cographs with cct. We also prove that deciding whether a perfect graph admits an sct is NP-complete. We characterize cographs with sct in terms of forbidden induced subgraphs; this characterization also leads to linear time recognition.