2026-07-26T02:38:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11545 2024-03-06T10:48:16Z ddc:004 open_access

When Maximum Stable Set Can Be Solved in FPT Time Bonnet, Édouard Bousquet, Nicolas Thomassé, Stéphan Watrigant, Rémi Parameterized Algorithms Independent Set H-Free Graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Nicolas Bousquet and Stéphan Thomassé and Rémi Watrigant 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.49 urn:nbn:de:0030-drops-115458 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.49 eng https://creativecommons.org/licenses/by/3.0/legalcode