Better lower and upper bounds for the minimum rainbow subgraph problem

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(nO(loglogn)).