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 for (sP:1+P_3) -free graphs for every integer (formula presented). We show the same result for the variants Connected Feedback Vertex Set and Connected Odd Cycle Transversal. For the latter two problems we also prove that they are polynomial-time solvable for cographs; this was known already for Feedback Vertex Set and Odd Cycle Transversal.
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest / Feghali, C.; Johnson, M.; Paesani, G.; Paulusma, D.. - 11651:(2019), pp. 258-273. ( International Symposium on Fundamentals of Computation Theory Copenhagen, Danimarca ) [10.1007/978-3-030-25027-0_18].
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Paesani G.;
2019
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 for (sP:1+P_3) -free graphs for every integer (formula presented). We show the same result for the variants Connected Feedback Vertex Set and Connected Odd Cycle Transversal. For the latter two problems we also prove that they are polynomial-time solvable for cographs; this was known already for Feedback Vertex Set and Odd Cycle Transversal.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
