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.2019.49
URN: urn:nbn:de:0030-drops-115458
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11545/
Bonnet, Édouard ;
Bousquet, Nicolas ;
Thomassé, Stéphan ;
Watrigant, Rémi
When Maximum Stable Set Can Be Solved in FPT Time
Abstract
Maximum Independent Set (MIS for short) is in general graphs the paradigmatic W[1]-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this paper, we introduce some variants of co-graphs with parameterized noise, that is, graphs that can be made into disjoint unions or complete sums by the removal of a certain number of vertices and the addition/deletion of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in H-free graphs. We show that for every fixed t >=slant 1, MIS is FPT in P(1,t,t,t)-free graphs, where P(1,t,t,t) is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size t. We also provide randomized FPT algorithms in dart-free graphs and in cricket-free graphs. This settles the FPT/W[1]-hard dichotomy for five-vertex graphs H.
BibTeX - Entry
@InProceedings{bonnet_et_al:LIPIcs:2019:11545,
author = {{\'E}douard Bonnet and Nicolas Bousquet and St{\'e}phan Thomass{\'e} and R{\'e}mi Watrigant},
title = {{When Maximum Stable Set Can Be Solved in FPT Time}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {49:1--49:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11545},
URN = {urn:nbn:de:0030-drops-115458},
doi = {10.4230/LIPIcs.ISAAC.2019.49},
annote = {Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs}
}
|
Keywords: |
|
Parameterized Algorithms, Independent Set, H-Free Graphs |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
