Independent Feedback Vertex Set for P5-free Graphs

Bonamy, M.; Dabrowski, K.K.; Feghali, C.; Johnson, M.; Paulusma, D.

Abstract

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.

Citation

Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0474-x

• Journal Article Type: Article
• Acceptance Date: Jun 16, 2018
• Online Publication Date: Jun 26, 2018
• Publication Date: Jun 1, 2018
• Deposit Date: Jun 18, 2018
• Publicly Available Date: Jun 18, 2018
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 81
• Issue: 4
• Pages: 1416-1449
• DOI: https://doi.org/10.1007/s00453-018-0474-x
• Public URL: https://durham-repository.worktribe.com/output/1328561