2001/01/01 by Subhash Khot · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Combinatorics #Binary logarithm #Graph #Log-log plot #Mathematics #Clique number #Graph coloring #Constant (computer programming) #Time complexity #Approximation algorithm #Clique #Upper and lower bounds #Discrete mathematics #Computer science
paper · doi:10.1109/sfcs.2001.959936
openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The author presents improved inapproximability results for three problems: the problem of finding the maximum clique size in a graph, the problem of finding the chromatic number of a graph, and the problem of coloring a graph with a small chromatic number with a small number of colors. J. Hastad's (1996) result shows that the maximum clique size in a graph with n vertices is inapproximable in polynomial time within a factor n/sup 1-/spl epsi// or arbitrarily small constant /spl epsi/>0 unless NP=ZPP. We aim at getting the best subconstant value of /spl epsi/ in Hastad's result. We prove that clique size is inapproximable within a factor n/2((log n))/sup 1-y/ corresponding to /spl epsi/=1/(log n)/sup /spl gamma// for some constant /spl gamma/>0 unless NP/spl sube/ZPTIME(2((log n))/sup O(1)/). This improves the previous best inapproximability factor of n/2/sup O(log n//spl radic/log log n)/ (corresponding to /spl epsi/=O(1//spl radic/log log n)) due to L. Engebretsen and J. Holmerin (2000). A similar result is obtained for the problem of approximating chromatic number of a graph. We also present a new hardness result for approximate graph coloring. We show that for all sufficiently large constants k, it is NP-hard to color a k-colorable graph with k/sup 1/25 (log k)/ colors. This improves a result of M. Furer (1995) that for arbitrarily small constant /spl epsi/>0, for sufficiently large constants k, it is hard to color a k-colorable graph with k/sup 3/2-/spl epsi// colors.