Fixed Parameter Inapproximability for Clique and SetCover in Time Super-exponential in OPT

2013/10/10 by Mohammad Taghi Hajiaghayi, Mohammad T. Hajiaghayi, Hajiaghayi, Mohammad T. +4
Computer Science · Engineering · #Advancements in Photolithography Techniques #Complexity and Algorithms in Graphs #Optimization and Search Problems #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.1310.2711

arxiv created 2013/12/05 · arxiv updated 2013/12/06

Abstract

In this paper, we consider proving inapproximability in terms of OPT and thus we base the foundations of fixed parameter inapproximability.

Related

• A Survey on Parameterized Inapproximability: k-Clique, k-SetCover, and More
• Parameterized Inapproximability Hypothesis under ETH
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
• PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability