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 2726678275 2069169607 1799262171
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. This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem. Given two graphs @math and @math , the Subgraph Isomorphism problem asks if @math is isomorphic to a subgraph of @math . While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time @math using the color-coding technique of Alon, Yuster, and Zwick; (2) in time @math using Courcelle's Theorem; (3) in time @math using a result on first-order model checking by Frick and Grohe; or (4) in time @math for connected @math using the algorithm of Matou s ek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of @math and @math (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time [ f_1(p_1,p_2,..., p_ ) n^ f_2(p_ +1 ,..., p_k) ] exist, where each of @math is one of the 10 parameters depending only on @math or @math . We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of @math gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when @math is a bounded-degree tree of constant pathwidth and @math is a planar graph of bounded pathwidth.