ALCOMFT-TR-01-184

Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Pino Persiano and Herve Rivano
Approximate Constrained Bipartite Edge Coloring
Patras. Work package 4. October 2001.

Abstract: We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard even for bipartite graphs of maximum degree three [F00].

In previous work Caragiannis et al. [CKP99] consider two special cases of the problem and proved tight bounds on the optimal number of colors by decomposing the bipartite graph into matchings which are colored into pairs using detailed potential and averaging arguments. Their techniques lead to 3/2-aproximation algorithms for both problems. In this paper we present a randomized (1.37+o(1))-approximation algorithm for the general problem in the case where max{l,c}=omega(\lnn). Our techniques are motivated by recent work of Kumar [K00] on the Circular Arc Coloring problem and are essentially different and simpler than those presented in [CKP99].

Postscript file: ALCOMFT-TR-01-184.ps.gz (65 kb).