Towards optimal lower bounds for clique and chromatic number

AbstractIt was previously known that neither Max Clique nor Min Chromatic Number can be approximated in polynomial time within n1−ε, for any constant ε>0, unless NP=ZPP. In this paper, we extend the reductions used to prove these results and combine the extended reductions with a recent result of Samorodnitsky and Trevisan to show that unless NP⊆ZPTIME(2O(logn(loglogn)3/2)), neither Max Clique nor Min Chromatic Number can be approximated in polynomial time within n1−ε(n) where ε∈O((loglogn)−1/2). Since there exists polynomial time algorithms approximating both problems within n1−ε(n) where ε(n)∈Ω(loglogn/logn), our result shows that the best possible ratio we can hope for is of the form n1−o(1), for some—yet unknown—value of o(1) between O((loglogn)−1/2) and Ω(loglogn/logn)