Publication details for Professor Matthew JohnsonBonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters 131: 26-32.
- Publication type: Journal Article
- ISSN/ISBN: 0020-0190
- DOI: 10.1016/j.ipl.2017.11.004
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.