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).
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)
|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
|Look up in GoogleScholar|