Skip to main content

Research Repository

Advanced Search

Independent feedback vertex sets for graphs of bounded diameter

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

Independent feedback vertex sets for graphs of bounded diameter Thumbnail


Authors

M. Bonamy

K.K. Dabrowski

C. Feghali



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
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 131
Pages 26-32
DOI https://doi.org/10.1016/j.ipl.2017.11.004

Files






You might also like



Downloadable Citations