Independent Feedback Vertex Set for P5-free Graphs

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

doi:10.4230/lipics.isaac.2017.16

Independent Feedback Vertex Set for P5-free Graphs

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

Authors

M. Bonamy

K. K. Dabrowski

C. Feghali

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Contributors

Yoshio Okamoto
Editor

Takeshi Tokuyama
Editor

Abstract

The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k ≥ 0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P4-free graphs. We show that it remains in P for P5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k ≥ 0.

Citation

Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Independent Feedback Vertex Set for P5-free Graphs. In Y. Okamoto, & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings (16:1-16:12). https://doi.org/10.4230/lipics.isaac.2017.16

Conference Name	ISAAC 2017
Publication Date	Jan 1, 2017
Deposit Date	Mar 5, 2018
Publicly Available Date	Apr 12, 2018
Volume	92
Pages	16:1-16:12
Series Title	Leibniz International Proceedings in Informatics
Series Number	92
Series ISSN	1868-8969
Book Title	28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings.
DOI	https://doi.org/10.4230/lipics.isaac.2017.16
Public URL	https://durham-repository.worktribe.com/output/1145868
Related Public URLs	http://drops.dagstuhl.de/opus/volltexte/2017/8230/

Files

Published Conference Proceeding (596 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
© Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma;
licensed under Creative Commons License CC-BY.