License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.16
URN: urn:nbn:de:0030-drops-82308
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8230/
Go to the corresponding LIPIcs Volume Portal

Bonamy, Marthe ; Dabrowski, Konrad K. ; Feghali, Carl ; Johnson, Matthew ; Paulusma, Daniël

Independent Feedback Vertex Set for P_5-free Graphs

pdf-format:
LIPIcs-ISAAC-2017-16.pdf (0.6 MB)

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 P_4-free graphs. We show that it remains in P for P_5-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.

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_5-free Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8230},
  URN =		{urn:nbn:de:0030-drops-82308},
  doi =		{10.4230/LIPIcs.ISAAC.2017.16},
  annote =	{Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph}
}

Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI