Feghali, C. and Johnson, M. and Paesani, G. and Paulusma, D. (2019) 'On cycle transversals and their connected variants in the absence of a small linear forest.', in Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings. Cham: Springer, pp. 258-273. Lecture notes in computer science. (11651).
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 (sP1+P3) -free graphs for every integer s≥1 . 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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (449Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1007/978-3-030-25027-0_18 |
| Publisher statement: | This is a post-peer-review, pre-copyedit version of an chapter published in the Fundamentals of Computation Theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-25027-0_18 |
| Date accepted: | 17 May 2019 |
| Date deposited: | 13 June 2019 |
| Date of first online publication: | 10 July 2019 |
| Date first made open access: | 13 November 2019 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
