Better lower and upper bounds for the minimum rainbow subgraph problem

In this paper we study the minimum rainbow subgraph problem, motivated by applications in bioinformatics. The input of the problem consists of an undirected graph with n vertices where each edge is colored with one of the p possible colors. The goal is to find a subgraph of minimum order (i.e. minimum number of vertices) which has precisely one edge from each color class. In this paper we show a randomized max(√2n,√δ(1+√lnδ/2))-approximation algorithm using LP rounding, where δ is the maximum degree in the input graph. On the other hand we prove that there exists a constant c such that the minimum rainbow subgraph problem does not have a clnδ-approximation, unless NP⊆DTIME(n^O(loglogn)).