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:

Independent feedback vertex set for P5-free graphs.

Bonamy, M. and Dabrowski, K.K. and Feghali, C. and Johnson, M. and Paulusma, D. (2017) 'Independent feedback vertex set for P5-free graphs.', in 28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16:1-16:12. Leibniz International Proceedings in Informatics., 92 (92).

Abstract

The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k ≥ 0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P4-free graphs. We show that it remains in P for P5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k ≥ 0.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(582Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.4230/LIPIcs.ISAAC.2017.16
Publisher statement:© Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma; licensed under Creative Commons License CC-BY.
Date accepted:No date available
Date deposited:12 April 2018
Date of first online publication:2017
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar