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.
Not every graph admits an independent feedback vertex set (consider complete graphs on at least four vertices). Graphs that do admit an independent feedback vertex set are said to be near-bipartite , and we can ask about the decision problem of recognising such graphs. Near-Bipartiteness a graph @math . is @math near-bipartite (that is, does @math have an independent feedback vertex set)? Near-Bipartiteness is -complete even for graphs of maximum degree @math @cite_0 and for graphs of diameter @math @cite_1 (see @cite_37 for a proof). Hence, by setting @math , we find that Independent Feedback Vertex Set is -complete for these two graph classes. The Independent Feedback Vertex Set problem is even -complete for planar bipartite graphs of maximum degree @math (see @cite_31 ). As bipartite graphs are near-bipartite, this result shows that there are classes of graphs where Independent Feedback Vertex Set is harder than Near-Bipartiteness . To obtain tractability results for Independent Feedback Vertex Set , we need to make some further assumptions.
@cite_0 @cite_31 @cite_37 @cite_1
2068819940 1491760138 2741305621 2726678275
For a given graph G, if the vertices of G can be partitioned into an independent set and an acyclic set, then we call G a near-bipartite graph. This paper studies the recognition of near-bipartite graphs. We give simple characterizations for those near-bipartite graphs having maximum degree at most 3 and those having diameter 2. We also show that the recognition of near-bipartite graphs is NP-complete even for graphs where the maximum degree is 4 or where the diameter is 4. 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. We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.