M. Bonamy
Independent feedback vertex sets for graphs of bounded diameter
Bonamy, M.; Dabrowski, K.K.; Feghali, C.; Johnson, M.; Paulusma, D.
Authors
K.K. Dabrowski
C. Feghali
Professor Matthew matthew.johnson2@durham.ac.uk
Head Of Department
Professor Daniel daniel.paulusma@durham.ac.uk
Professor
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 |
Files
Published Journal Article
(399 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Accepted Journal Article
(330 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright 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/).
You might also like
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Computing weighted subset odd cycle transversals in H-free graphs
(2022)
Journal Article
Computing subset transversals in H-free graphs
(2021)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search