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.IPEC.2018.17
URN: urn:nbn:de:0030-drops-102183
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10218/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Bousquet, Nicolas ; Charbit, Pierre ; Thomassé, Stéphan ; Watrigant, Rémi

Parameterized Complexity of Independent Set in H-Free Graphs

pdf-format:
LIPIcs-IPEC-2018-17.pdf (0.5 MB)

Abstract

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.

BibTeX - Entry

@InProceedings{bonnet_et_al:LIPIcs:2019:10218,
  author =	{{\'E}douard Bonnet and Nicolas Bousquet and Pierre Charbit and St{\'e}phan Thomass{\'e} and R{\'e}mi Watrigant},
  title =	{{Parameterized Complexity of Independent Set in H-Free Graphs}},
  booktitle =	{13th International Symposium on Parameterized and Exact  Computation (IPEC 2018)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Christophe Paul and Michal Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10218},
  URN =		{urn:nbn:de:0030-drops-102183},
  doi =		{10.4230/LIPIcs.IPEC.2018.17},
  annote =	{Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs}
}

Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs
Collection: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Issue Date: 2019
Date of publication: 05.02.2019

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