Parameterized complexity of independent set in H-free graphs

DOI10.1007/s00453-020-00730-6zbMath1452.68090arXiv1810.04620MaRDI QIDQ786045

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

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.04620

zbMATH Keywords

independent set; parameterized algorithms; H-free graphs

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68Q27: Parameterized complexity, tractability and kernelization