On hardness of approximating the parameterized clique problem

DOI10.1145/2840728.2840733MaRDI QIDQ2800551zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Igor Shinkar

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

cliqueparameterized complexityhardness of approximationfixed parameter tractability

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)

Recommendations

• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• The parameterized complexity of the k-biclique problem
• Linear FPT reductions and computational lower bounds
• The parameterized complexity of k-biclique
• scientific article; zbMATH DE number 1670809

Cited in

(12)

• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• On the complexity of fixed parameter clique and dominating set
• The parameterized complexity of the k-biclique problem
• On NP-hardness of the clique partition -- independence number gap recognition and related problems
• The exponential time hypothesis and the parameterized clique problem
• New tools and connections for exponential-time approximation
• On the query complexity of clique size and maximum satisfiability
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• On approximating the number of k-cliques in sublinear time
• Interactive proofs and the hardness of approximating cliques

This page was built for publication: On hardness of approximating the parameterized clique problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800551)