SCIENCE@home

Towards optimal lower bounds for clique and chromatic number

Lars Engebretsen,Jonas Holmerin

Published 2003 in Theoretical Computer Science

ABSTRACT

It was previously known that neither Max Clique nor Min Chromatic Number can be approximated in polynomial time within n1-e, for any constant e > 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(log n(log log n)3/2)), neither Max Clique nor Min Chromatic Number can be approximated in polynomial time within n1-e(n) where e ∈ O((log log n)-1/2). Since there exists polynomial time algorithms approximating both problems within n1-e(n) where e(n) ∈ Ω(log log n/log n), 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((log log n)-1/2) and Ω(log log n/log n).

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-32 of 32 references · Page 1 of 1

CITED BY

Showing 1-34 of 34 citing papers · Page 1 of 1