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

Feghali, C.; Johnson, M.; Paesani, G.; Paulusma, D.

doi:10.1007/978-3-030-25027-0_18

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

Feghali, C.; Johnson, M.; Paesani, G.; Paulusma, D.

Authors

C. Feghali

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

G. Paesani

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Contributors

Leszek Antoni Gąsieniec
Editor

Jesper Jansson
Editor

Christos Levcopoulos
Editor

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.

Citation

Feghali, C., Johnson, M., Paesani, G., & Paulusma, D. (2019). On cycle transversals and their connected variants in the absence of a small linear forest. In L. A. Gąsieniec, J. Jansson, & C. Levcopoulos (Eds.), Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings (258-273). https://doi.org/10.1007/978-3-030-25027-0_18

Conference Name	FCT 2019
Conference Location	Copenhagen, Denmark
Start Date	Aug 11, 2019
End Date	Aug 14, 2019
Acceptance Date	May 17, 2019
Online Publication Date	Jul 10, 2019
Publication Date	Jul 10, 2019
Deposit Date	Jun 12, 2019
Publicly Available Date	Nov 13, 2019
Publisher	Springer Verlag
Pages	258-273
Series Title	Lecture notes in computer science
Series Number	11651
Book Title	Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings.
ISBN	9783030250263
DOI	https://doi.org/10.1007/978-3-030-25027-0_18
Public URL	https://durham-repository.worktribe.com/output/1142630

Files

Accepted Conference Proceeding (459 Kb)
PDF

Copyright 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