Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Daniel (2018) 'Independent feedback vertex set for P5-free graphs.', Algorithmica., 81 (4). pp. 1416-1449.
The NP-complete problem Feedback Vertex Set is that of deciding whether or not 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 whether or not 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 polynomial-time solvable for P5 -free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most k for a given integer k≥0 . Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for H-free graphs with the complexity of 3-Colouring, Independent Odd Cycle Transversal and other related problems.
|Full text:||(AM) Accepted Manuscript|
Download PDF (449Kb)
|Full text:||(VoR) Version of Record|
Available under License - Creative Commons Attribution.
Download PDF (Advance online version) (776Kb)
|Publisher Web site:||https://doi.org/10.1007/s00453-018-0474-x|
|Publisher statement:||© The Author(s) 2018. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.|
|Date accepted:||16 June 2018|
|Date deposited:||18 June 2018|
|Date of first online publication:||26 June 2018|
|Date first made open access:||29 June 2018|
Save or Share this output
|Look up in GoogleScholar|