The Complexity of Near-Optimal Graph Coloring

ABSTRACT

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 &khgr;(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) = &khgr;(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 < 2 and constant d there exists a polynomial-time algorithm A which guarantees A(G) ≤ r·&khgr;(G) + d, then there also exists a polynomial-time algorithm A which guarantees A(G) = &khgr;(G).

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: GAREY, M R, JOHNSON, D. S, AND STOCKMEYER, L. Some slmphfied NP-complete graph problems Theor Comput Sei (to appear).
• 3: GaA~AM, R. L Bounds on multlprocessing timing anomahes SIAM J on Appl. Math. 17 (1969), 416-429.
• 4: HILTON, A J. W., RADO, R., AND SCOTT, S. H. A (<5)-colour theorem for planar graphs. Bull. London Math. Soc. 5 (1973), 302-306.
• 5: BARRA, O I-I , AND KIM, C.E. Fast approximation algorithms for the knapsack and sum of ubset problems Tech. Rep 74-13, Dep of Computer, Informatmn, and Control Sciences, U. of Minnesota, Mmneapohs, Minn., 1974.
• 6: JOHNSON, D.S. Approximation algomthms for combmatomal problems J. Comput. and Syst. Sc~s 9 (1974), 256-278
• 7: JOHNSON, D. S Worst case behavior of graph coloring algorithms Proc of the Fifth Southeastern Conf on Combmatorlcs, Graph Theory, and Computing, Utflltas Mathemat~ca Pubfishing, Winmpeg, Canada, 1974, pp 513-528.
• 8: JOHNSON, D S , DEMERS, A, ULLMAN, J D , GAREY, M. R , AND GRAHAM, R. L Worst-case performance bounds for simple one-dimensional packing algomthms SIAM J Comput. 8 (1974), 299-326
• 9: KARP, R M Reduclblhty among combmatomal problems. In Complexzty of Computer Computations, R E. Miller and J W. Thatcher, Eds, Plenum Press, New York, 1972, pp 85-104.
• 10: Lov~-sz, L. (Personal commumcation.)
• 11: MATULA, D. M, MARBLE, G, AND ISAACSON, J D Graph coloring algorithms In Graph Theory and Computing, R. C Read, Ed., Academic Press, New York, 1972, pp 109-122.
• 12: ROSI!INKRANTZ, D J., STEARNS, R. E, AND LEWIS, P M Approximate algorithms for the traveling salesperson problem Proc 15th Annual Symp. on Switching and Automata Theory, IEEE, 1974, pp 33-42
• 13: SAHNI, S, AND GONZALES, T. P-Complete problems and approximate solutions Proc. 15th Annual Symp on Switching and Automata Theory, IEEE, 1974, pp. 28-32
• 14: Larry Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, v.5 n.3, p.19-25, July 1973 [doi>10.1145/1008293.1008294]
• 15: WELSH, D J A., AND POWELL, M. B An upper bound to the chromatic number of a graph and its apphcatlon to time tabhng problems Comput J 10 (1967), 85-86.
• 16: WOOD, D. C. A techmque for coloring a graph apphcable to large scale tlme-tabhng problems. Comput. J 12 (1969), 317-319

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
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory, Verification