An asymptotic approximation scheme for multigraph edge coloring

ABSTRACT

The edge coloring problem asks for assigning colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, i.e., parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. Our algorithms achieve arbitrarily good approximation factors at the cost of slightly larger additive terms. In particular, for any ∈ > 0 we achieve a solution quality of (1 + ∈)opt + O(1/∈). The execution times of one algorithm are independent of ∈ and polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.

REFERENCES

• 1: Alberto Caprara , Romeo Rizzi, Improving a family of approximation algorithms to edge color multigraphs, Information Processing Letters, v.68 n.1, p.11-15, Oct. 15, 1998 [doi>10.1016/S0020-0190(98)00138-0]
• 2: R. Cole, K. Ost, and S. Schirra. Edge-coloring bipartite multigraphs in O(E logD) time. Combinatorica, 21(1):5--12, 2000.
• 3: Uriel Feige , Eran Ofek , Udi Wieder, Approximating Maximum Edge Coloring in Multigraphs, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.108-121, September 17-21, 2002
• 4: M. K. Goldberg. On multigraphs of almost maximal chromatic class (in russian). Diskret Analiz, 23:3--7, 1973.
• 5: Dorit S Hochbaum , Takao Nishizeki , David B Shmoys, A better than “best possible” algorithm to edge color multigraphs, Journal of Algorithms, v.7 n.1, p.79-104, March 1986 [doi>10.1016/0196-6774(86)90039-8]
• 6: I. Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718--720, 1981.
• 7: Jeff Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory Series B, v.68 n.2, p.233-254, Nov. 1996 [doi>10.1006/jctb.1996.0067]
• 8: Takao Nishizeki , Kenichi Kashiwagi, On the 1.1 edge-coloring of multigraphs, SIAM Journal on Discrete Mathematics, v.3 n.3, p.391-410, Aug. 1990 [doi>10.1137/0403035]
• 9: M. W. Padberg and L. A. Wolsey. Fractional covers for forests and matchings. Math. Programming, 29(1):1--14, 1984.
• 10: Michael Plantholt, A sublinear bound on the chromatic index of multigraphs, Discrete Mathematics, v.202 n.1-3, p.201-213, May 6, 1999 [doi>10.1016/S0012-365X(98)00356-2]
• 11: M. Plantholt. A combined logarithmic bound on the chromatic index of multigraphs. manuscript in preparation. The result was presented at the 34th Southeastern Int. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, 2003.
• 12: P. D. Seymour. Some unsolved problems on one-factorization of graphs. In J. A. Bondy and U. S. R. Murty, editors, Graph Theory and Related Topics, pages 367--368. Academic Press, 1979.
• 13: V. G. Vizing. On an estimate of the chromatic class of a p-graph (in russian). Diskret. Analiz, 3:23--30, 1964.