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.
There has been much recent interest in coloring graphs which are already known to be colorable while minimizing the number of colors used. For a 3-colorable graph, Wigderson gave an algorithm using at most @math colors @cite_24 , which Blum improved to @math @cite_23 . A line of research improved this bound still further to @math @cite_28 . Despite the difficulties in improving the constant in the exponent, and as suggested by Arora @cite_22 , there is no evidence that coloring a 3-colorable graph with as few as @math colors is hard.
@cite_24 @cite_28 @cite_22 @cite_23
1982506822 1529433769 1947552815 2036660814
The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it uses on the input graph and the chromauc number of this graph. The previous best known polynomial-time algorithm had a performance guarantee O(n logn) for graphs on n vertices. This result stood unchallenged for eight years. This paper presents an efficient algorithm with performance guarantee of O(n(loglog n)2 (logn)2). We show how the results of Karger, Motwani, and Sudan (1994) and Blum (1994) can be combined in a natural manner to yield a polynomial-time algorithm for O(n314)-coloring any n-node 3-colorable graph. This improves on the previous best bound of O(n14) colors (, 1994). How to color 3 colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses n0.2072 colors. There are no indications that coloring using say O(log n) colors is hard. It has been suggested that SDP hierarchies could be used to design algorithms that use ne colors for arbitrarily small e > 0. We explore this possibility in this paper and find some cause for optimism. While the case of general graphs is till open, we can analyse the Lasserre relaxation for two interesting families of graphs. For graphs with low threshold rank (a class of graphs identified in the recent paper of Arora, Barak and Steurer on the unique games problem), Lasserre relaxations can be used to find an independent set of size Ω(n) (i.e., progress towards a coloring with O(log n) colors) in nO(D) time, where D is the threshold rank of the graph. This algorithm is inspired by recent work of Barak, Raghavendra, and Steurer on using Lasserre Hierarchy for unique games. The algorithm can also be used to show that known integrality gap instances for SDP relaxations like strict vector chromatic number cannot survive a few rounds of Lasserre lifting, which also seems reason for optimism. For distance transitive graphs of diameter Δ, we can show how to color them using O(log n) colors in n2O(Δ) time. This family is interesting because the family of graphs of diameter O(1 e) is easily seen to be complete for coloring with ne colors. The distance-transitive property implies that the graph "looks" the same in all neighborhoods. The full version of this paper can be found at: http: www.cs.princeton.edu rongge LasserreColoring.pdf . The problem of coloring a graph with the minimum number of colorsis well known to be NP-hard, even restricted to k -colorable graphs for constant k ≥ 3. This paper explores theapproximation problem of coloring k -colorable graphs with as fewadditional colors as possible in polynomial time, with special focus onthe case of k = 3. The previous best upper bound on the number of colors needed forcoloring 3-colorable n -vertex graphsin polynomial time was o n log n colors by Berger and Rompel, improving a bound of o n colors by Wigderson. This paper presents an algorithmto color any 3-colorable graph with o n3 8 polylog n colors, thus breaking an“ O((n 1 2-o(1) ) barrier”. The algorithm given here is based on examiningsecond-order neighborhoods of vertices, rather than just immediateneighborhoods of vertices as in previous approaches. We extend ourresults to improve the worst-case bounds for coloring k -colorable graphs for constant k > 3 as well.