Approximate graph coloring by semidefinite programming

ABSTRACT

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with min{O(&Dgr;1/3 log1/2 &Dgr; log n), O(n1/4 log1/2 n)} colors where &Dgr; is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first nontrivial approximation result as a function of the maximum degree &Dgr;. This result can be generalized to k-colorable graphs to obtain a coloring using min{O(&Dgr;1-2/k log1/2 &Dgr; log n), O(n1−3/(k+1) log1/2 n)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovász &thgr;-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the &thgr;-function.

REFERENCES

• 1: ALDOUS, D. 1989. Probability Approximations via the Poisson Clumping Heuristic. Springer-Verlag, New York.
• 2: ALIZADEH, F. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 1, 13-51.
• 3: Noga Alon , Nabil Kahale, A spectral technique for coloring random 3-colorable graphs (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.346-355, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195187]
• 4: Noga Alon , Nabil Kahale, Approximating the independence number via the j -function, Mathematical Programming: Series A and B, v.80 n.3, p.253-264, Feb. 1, 1998 [doi>10.1007/BF01581168]
• 5: ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1992. Proof verification and hardness of approximation problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 14-23.
• 6: Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
• 7: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 8: Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
• 9: 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]
• 10: Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
• 11: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 12: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 13: CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, P.W. 1981. Register allocation via coloring. Comput. Lang. 6, 47-57.
• 14: FELLER, W. 1968. An Introduction to Probability Theory and Its Applications. Wiley, New York.
• 15: FRANKL, P., AND RODL, V. 1994. Forbidden intersections. Trans. AMS. 300, 259-286.
• 16: Uriel Feige, Randomized graph products, chromatic numbers, and Lovasz j-function, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.635-640, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225281]
• 17: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 18: Uriel Feige , Joe Kilian, Zero Knowledge and the Chromatic Number, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.278, May 24-27, 1996
• 19: FRIEZE, A., AND JERRUM, M. 1994. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Manuscript.
• 20: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 21: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 22: GOLUB, G. H., AND VAN LOAN, C.F. 1983. Matrix Computations. Johns Hopkins University Press, Baltimore, Md.
• 23: GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its consequences in combinatorial optimization, combinatorica 1, 169-197.
• 24: GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1987. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.
• 25: Magnús M. Hallórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, v.45 n.1, p.19-23, Jan. 25, 1993 [doi>10.1016/0020-0190(93)90246-6]
• 26: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 27: JOHNSON, D.S. 1974. Worst case behavior of graph coloring algorithms. In Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium X, pp. 513-527.
• 28: KHANNA, S., LINIAL, N., AND SAFRA, S. 1992. On the hardness of approximating the chromatic number. In Proceedings of the 2nd Israeli Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 250-260.
• 29: KHANNA, S., MOTWANI, R., SUDAN, M., AND VAZIRANI, U. 1994. On syntactic versus computational views of approximability. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 819-830.
• 30: KNESER, M. 1955. Aufgabe 300. Jber. Deutsch. Math.-Verein. 58.
• 31: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 32: KNUTH, D.E. 1994. The sandwich theorem. Elect. J. Combin. 1, 1-48.
• 33: LovAsz, L. 1979. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1-7.
• 34: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
• 35: S. Mahajan , H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.162, October 23-25, 1995
• 36: MILNER, E. C. 1968. A combinatorial theorem on systems of sets. J. London Math. Soc. 43, 204 -206.
• 37: MOTWANI, R., AND NAOR, J. 1993. On exact and approximate cut covers of graphs. Manuscript.
• 38: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 39: R#NYI, A. 1970. Probability Theory. Elsevier, New York.
• 40: SZEGEDY, M. 1994. A note on the 0 number of Lovfisz and the generalized Delsarte bound. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 36-39.
• 41: Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]
• 42: WooD, D. C. 1969. A technique for coloring a graph applicable to large-scale optimization problems. Comput. J. 12, 317.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory

Keywords:
NP-completeness, approximation algorithms, chromatic number, graph coloring, randomized algorithms