Towards optimal lower bounds for clique and chromatic number

✍ Scribed by Lars Engebretsen; Jonas Holmerin

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 426 KB
• Volume: 299
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00535-2

✦ Synopsis

It was previously known that neither Max Clique nor Min Chromatic Number can be approximated in polynomial time within n 1-, 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(2 O(log n(log log n) 3=2 ) ), neither Max Clique nor Min Chromatic Number can be approximated in polynomial time within n 1- (n) where ∈ O((log log n) -1=2 ). Since there exists polynomial time algorithms approximating both problems within n 1-(n) where (n) ∈ (log log n=log n), our result shows that the best possible ratio we can hope for is of the form n 1-o(1) , for some-yet unknown-value of o(1) between O((log log n) -1=2 ) and (log log n=log n).