Independent feedback vertex sets for graphs of bounded diameter

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

Abstract

The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2.

Citation

Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131, 26-32. https://doi.org/10.1016/j.ipl.2017.11.004

• Journal Article Type: Article
• Acceptance Date: Nov 13, 2017
• Online Publication Date: Nov 16, 2017
• Publication Date: Mar 1, 2018
• Deposit Date: Nov 15, 2017
• Publicly Available Date: Nov 15, 2017
• Journal: Information Processing Letters
• Print ISSN: 0020-0190
• Electronic ISSN: 1872-6119
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 131
• Pages: 26-32
• DOI: https://doi.org/10.1016/j.ipl.2017.11.004
• Public URL: https://durham-repository.worktribe.com/output/1343711