Bonamy, Marthe ;
Dabrowski, Konrad K. ;
Feghali, Carl ;
Johnson, Matthew ;
Paulusma, Daniël
Independent Feedback Vertex Set for P_5free Graphs
Abstract
The NPcomplete 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 NPcomplete. In fact, even deciding if an independent feedback vertex set exists is NPcomplete and this problem is closely related to the 3Colouring 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 Hfree graphs. We prove that it is NPcomplete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomialtime solvable for P_4free graphs. We show that it remains in P for P_5free 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.
BibTeX  Entry
@InProceedings{bonamy_et_al:LIPIcs:2017:8230,
author = {Marthe Bonamy and Konrad K. Dabrowski and Carl Feghali and Matthew Johnson and Dani{\"e}l Paulusma},
title = {{Independent Feedback Vertex Set for P_5free Graphs}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {16:116:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8230},
URN = {urn:nbn:de:0030drops82308},
doi = {10.4230/LIPIcs.ISAAC.2017.16},
annote = {Keywords: feedback vertex set, odd cycle transversal, independent set, Hfree graph}
}
07.12.2017
Keywords: 

feedback vertex set, odd cycle transversal, independent set, Hfree graph 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 