Approximation algorithms for the minimum rainbow subgraph problem

We consider the minimum rainbow subgraph   problem (MRS): given a graph GG, whose edges are coloured with pp colours. Find a subgraph F⊆GF⊆G of GG of minimum order and with pp edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G)Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G)Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of 56Δ for Δ≥2Δ≥2.