Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s≥1, both problems are polynomial-time solvable for sP3-free graphs and (sP1+P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1+P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., TCS 2018], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica 2020] and P5-free graphs [Abrishami et al., SODA 2021]. Together, the new results also show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1+P5)-free graph G a largest induced subgraph whose blocks belong to some finite class C of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs.
