Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Independent feedback vertex sets for graphs of bounded diameter.

Bonamy, M. and Dabrowski, K.K. and Feghali, C. and Johnson, M. and Paulusma, D. (2018) 'Independent feedback vertex sets for graphs of bounded diameter.', Information processing letters., 131 . pp. 26-32.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
(323Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(390Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.ipl.2017.11.004
Publisher statement:© 2017 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Date accepted:13 November 2017
Date deposited:15 November 2017
Date of first online publication:16 November 2017
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar