Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

On cycle transversals and their connected variants in the absence of a small linear forest.

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:
Export
Look up in GoogleScholar