The labeled perfect matching in bipartite graphs

In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function L:E→{c1,…,cq}, the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors.