×

Approximation results for the minimum graph coloring problem. (English) Zbl 0806.68085

We devise a new polynomial time approximation algorithm for the minimum vertex coloring problem. We analyze the approximation performance of this algorithm by using a new approximation measure, namely the ratio \([\omega(I) - \lambda(I)]/[\omega(I) - \beta(I)]\), called differential approximation ratio, where, for an instance \(I\), \(\omega(I)\) (resp. \(\lambda(I)\), \(\beta(I)\)) is the cardinality of the worst case (resp. approximated, optimal) solution of an instance \(I\) of the problem. We prove that the differential approximation ratio of the minimum vertex coloring problem is bounded below by 1/2 (in the framework of the classical approximation theory, vertex coloring is not constant- approximable). We also prove that this bound is tight for the algorithm. We show that the problem does not admit differential polynomial time approximation schema. Finally, we devise differential-ratio-preserving reductions linking vertex coloring to vertex covering by cliques and edge covering by cliques problems. A consequence of these reductions is that the differential approximation ratio for vertex coloring is transferred to the latter problems.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[2] Kou, L. T.; Stockmeyer, L. J.; Wong, C. K., Covering edges by cliques with regard to keyword conflicts and intersection graphs, Comm. ACM, 21, 135-139 (1978) · Zbl 0367.68035
[3] Lund, C.; Yannakakis, M., On the hardness of aprroximating minimization problems, Proc. ACM/STOC, 286-293 (1993) · Zbl 1310.68094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.