On Hardness of Approximating the Parameterized Clique Problem

DOI10.1145/2840728.2840733zbMath1334.68088MaRDI QIDQ2800551

Igor Shinkar, Subhash A. Khot

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2840728.2840733

zbMATH Keywords

fixed parameter tractability; clique; hardness of approximation; parameterized complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

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