We introduce a new notion of resilience for constraint satisfaction problems, with the goal of more precisely determining the boundary between NP-hardness and the existence of efficient algorithms for resilient instances. In particular, we study @math -resiliently @math -colorable graphs, which are those @math -colorable graphs that remain @math -colorable even after the addition of any @math new edges. We prove lower bounds on the NP-hardness of coloring resiliently colorable graphs, and provide an algorithm that colors sufficiently resilient graphs. We also analyze the corresponding notion of resilience for @math -SAT. This notion of resilience suggests an array of open questions for graph coloring and other combinatorial problems.
On the other hand there are asymptotic and concrete lower bounds. Khot @cite_9 proved that for sufficiently large @math it is NP-hard to color a @math -colorable graph with fewer than @math colors; this was improved by Huang to @math @cite_25 . It is also known that for every constant @math there exists a sufficiently large @math such that coloring a @math -colorable graph with @math colors is NP-hard @cite_20 . In the non-asymptotic case, Khanna, Linial, and Safra @cite_2 used the PCP theorem to prove it is NP-hard to 4-color a 3-colorable graph, and more generally to color a @math colorable graph with at most @math colors. Guruswami and Khanna give an explicit reduction for @math @cite_4 . Assuming a variant of Khot's 2-to-1 conjecture, prove that distinguishing between chromatic number @math and @math is hard for constants @math @cite_20 . This is the best conditional lower bound we give in , but it does not to our knowledge imply Theorem .
@cite_4 @cite_9 @cite_2 @cite_25 @cite_20
1969999211 2132991500 2104254886 1492972816
We give a new proof showing that it is NP-hard to color a 3-colorable graph using just 4 colors. This result is already known , [S. Khanna, N. Linial, and S. Safra, Combinatorica, 20 (2000), pp. 393--415], but our proof is novel because it does not rely on the PCP theorem, while the known one does. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor @math hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem [M. Bellare, O. Goldreich, and M. Sudan, SIAM J. Comput., 27 (1998), pp. 805--915]. Another aspect in which our proof is novel is in its use of the PCP theorem to show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs (this hardness result does not seem to follow from the earlier reduction of Khanna, Linial, and Safra). We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires @math colors. Our proof technique also shows that there is an @math such that it is NP-hard to legally 4-color even a @math fraction of the edges of a 3-colorable graph. 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. The paper considers the computational hardness of approximating the chromatic number of a graph. The authors first give a simple proof that approximating the chromatic number of a graph to within a constant power (of the value itself) in NP-hard. They then consider the hardness of coloring a 3-colorable graph with as few as possible colors. They show that determining whether a graph is 3-colorable or any legal coloring of it requires at least 5 colors is NP-hard. Therefore, coloring a 3-colorable graph with 4 colors is NP-hard. > We prove that for sufficiently large K, it is NP-hard to color K-colorable graphs with less than (2^ (K^ 1 3 ) ) colors. This improves the previous result of K versus (K^ 1 25 K ) in Khot [1].