Conditional hardness for approximate coloring

ABSTRACT

We study the APPROXCOLORING q(Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q. We derive conditional hardness for this problem for any constant 3 ≤ q < Q. For q ≥ 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness result on a certain 'fish shaped' variant of his conjecture.We also prove that the problem ALMOST-3-COLORING_ε is hard for any constant ε>0, assuming Khot's Unique Games conjecture. This is the problem of deciding for a given graph, between the case where one can 3-color all but a ε fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least ε.Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

REFERENCES

• 1: N. Alon, I. Dinur, E. Friedgut, and B. Sudakov. Graph products, fourier analysis and spectral techniques. GAFA, 14(5):913--940, 2004.
• 2: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 3: Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
• 4: C. Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1--13, 1985.
• 5: M. Charikar, K. Makarychev, and Y. Makarychev. Approximating unique games. In private communication, 2005.
• 6: I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1), 2005.
• 7: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 8: M. Furer, Improved hardness results for approximating the chromatic number, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.414, October 23-25, 1995
• 9: Anupam Gupta , Kunal Talwar, Approximating unique games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.99-106, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109569]
• 10: Venkatesan Guruswami , Sanjeev Khanna, On the Hardness of 4-Coloring a 3-Colorable Graph, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.188, July 04-07, 2000
• 11: Eran Halperin , Ram Nathaniel , Uri Zwick, Coloring k-colorable graphs using relatively small palettes, Journal of Algorithms, v.45 n.1, p.72-90, October 2002 [doi>10.1016/S0196-6774(02)00217-1]
• 12: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 13: David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998 [doi>10.1145/274787.274791]
• 14: S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. Combinatorica, 20(3):393--415, 2000.
• 15: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 16: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 17: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 18: S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. In Proc. of 18th IEEE Annual Conference on Computational Complexity (CCC), pages 379--386, 2003.
• 19: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 20: Y. Rinott and V. Rotar'. A remark on quadrant normal probabilities in high dimensions. Statistics and Probability Letters, 51(1):47--51, 2001.
• 21: Luca Trevisan, Approximation Algorithms for Unique Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.197-205, October 23-25, 2005 [doi>10.1109/SFCS.2005.22]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
graph coloring, hardness of approximation, unique games conjecture