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 \geq 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., Theoret. Comput. Sci., 705 (2018), pp. 75--83], (sP1 +P3)-free graphs [Dabrowski et al., Algorithmica, 82 (2020), pp. 2841--2866] and P5-free graphs [Abrishami et al., Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 1948-1964]. Together, the new results also show that both problems exhibit the same behavior 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 \scrC 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.