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.

@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}
}