Publication details for Professor Matthew JohnsonBonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2017), Independent Feedback Vertex Set for P5-free Graphs, in Okamoto, Yoshio & Tokuyama, Takeshi eds, Leibniz International Proceedings in Informatics 92: ISAAC 2017. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 16:1-16:12.
- Publication type: Conference Paper
- ISSN/ISBN: 1868-8969, 9783959770545
- DOI: 10.4230/LIPIcs.ISAAC.2017.16
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
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.