On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
arXiv:1908.00491
The paper establishes polynomial‑time algorithms for Feedback Vertex Set, Odd Cycle Transversal and their connected variants on (sP1+P3)-free graphs and cographs, and shows NP‑completeness of the odd cycle transversal problems on certain small‑forest‑free graph classes.
Abstract
A graph is $H$-free if it contains no induced subgraph isomorphic to $H$. We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and Odd Cycle Transversal by showing that they can be solved in polynomial time on $(sP_1+P_3)$-free graphs for every integer $s\geq 1$. We show the same result for the variants Connected Feedback Vertex Set and Connected Odd Cycle Transversal. We also prove that the latter two problems are polynomial-time solvable on cographs; this was already known for Feedback Vertex Set and Odd Cycle Transversal. We complement these results by proving that Odd Cycle Transversal and Connected Odd Cycle Transversal are NP-complete on $(P_2+P_5,P_6)$-free graphs.
21 pages, 5 figures