On Hardness of Approximating the Parameterized Clique Problem

DOI10.1145/2840728.2840733zbMath1334.68088OpenAlexW2295669206MaRDI 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 tractabilitycliquehardness of approximationparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ New tools and connections for exponential-time approximation

This page was built for publication: On Hardness of Approximating the Parameterized Clique Problem