New approximation algorithms for graph coloring

ABSTRACT

The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k ≥ 3. This paper explores the approximation problem of coloring k-colorable graphs with as few additional colors as possible in polynomial time, with special focus on the case of k = 3. The previous best upper bound on the number of colors needed for coloring 3-colorable n-vertex graphs in polynomial time was on/logn colors by Berger and Rompel, improving a bound of on colors by Wigderson. This paper presents an algorithm to color any 3-colorable graph with on^{3/8polylog n} colors, thus breaking an “O((n1/2-&ogr;(1)) barrier”. The algorithm given here is based on examining second-order neighborhoods of vertices, rather than just immediate neighborhoods of vertices as in previous approaches. We extend our results to improve the worst-case bounds for coloring k-colorable graphs for constant k > 3 as well.

REFERENCES

• 1: ~ANGLUIN, D., AND VALIANT, L.G. 1979. Fast probabilistic algorithms for Hamiltonian circuits ~and matchings. J. Comput. Syst. Sci. 18, 2 Apr., 155-193.
• 2: ~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 Symposium on Founda- ~tions of Computer Science (Pittsburg, Pa., Oct.) IEEE, New York, pp. 14-23.
• 3: ~BAR-YEHUDA, R., AND EVEN S. 1985. A local-ratio theorem for approximating the weighted ~vertex cover problem. Ann. Dis. Math. 25 (1985), 27-46.
• 4: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 5: ~BERGER, B., AND ROMPEL J. 1990. A better performance guarantee for approximate graph ~coloring. Algonthmica 5, 459-466.
• 6: A. Blum, An O(n^0.4)-approximation algorithm for 3-coloring, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.535-542, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73058]
• 7: ~BLUM, A. 1992. Some tools for approximate 3-coloring. In Proceedings of the 31st ,4nnual ~Symposium old Foundations of Computer Science (St. Louis, Mo., Oct.) IEEE, New York, pp. ~554-562.
• 8: Avrim Louis Blum, Algorithms for approximate graph coloring, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 9: R. Boppana , M. M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, Proceedings of the second Scandinavian workshop on Algorithm theory, p.13-25, July 1990, Bergen, Sweden
• 10: 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
• 11: 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
• 12: ~CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, m. K., COCKE, J., HOPKINS, M. E., AND ~MAI~KSTEIN, P.W. 1981. Rcgistcr allocation via coloring. Cornput. Lang. 6 47-57.
• 13: M. E. Dyer , A. M. Frieze, The solution of some random NP-hard problems in polynomial expected time, Journal of Algorithms, v.10 n.4, p.451-489, Dec. 1989 [doi>10.1016/0196-6774(89)90001-1]
• 14: 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]
• 15: ~KUCERA, L. 1977. Expected behavior of graph colouring algorithms. In Lecture Notes In ~Computer Sctence, Vol. 56. Springer-Verlag, New York, pp. 447-457.
• 16: 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]
• 17: Burkhard Monien , Ewald Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem, Acta Informatica, v.22 n.1, p.115-123, April 1985 [doi>10.1007/BF00290149]
• 18: ~NELSON, R., AND WILSON, R. J., EDS. 1990. Graph Colounngs. Longman Scientific and Techni- ~cal. Hardon, Essex, United Kingdom.
• 19: Jonathan S. Turner, Almost all k-colorable graphs are easy to color, Journal of Algorithms, v.9 n.1, p.63-82, March 1988 [doi>10.1016/0196-6774(88)90005-3]
• 20: ~VlSHWAN^THAN, S. 1990. Randomized online graph coloring (preliminary version). In Proceed- ~ings of tile 31st Annual Symposium on Foundations of Computer Science, (St. Louis, Oct.). IEEE, ~New York, pp. 464 469.
• 21: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, chromatic number, graph coloring