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
1969999211 2036660814 2025904765 2079035346
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 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. Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and partitioning problems. In this paper the complexity and performance of algorithms which construct such colorings are investigated. For a graph G , let k( G ) denote the minimum possible number of colors required to color G and, for any graph coloring algorithm A , let A ( G ) denote the number of colors used by A when applied to G . Since the graph coloring problem is known to be “NP-complete,” it is considered unlikely that any efficient algorithm can guarantee A ( G ) = k( G ) for all input graphs. In this paper it is proved that even coming close to khgr;( G ) with a fast algorithm is hard. Specifically, it is shown that if for some constant r d there exists a polynomial-time algorithm A which guarantees A ( G ) ≤ r ·k( G ) + d , then there also exists a polynomial-time algorithm A which guarantees A ( G ) = k( G ). Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p @math c n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p @math polylog(n) n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.