Improved approximation bounds for the minimum rainbow subgraph problem
In this paper we consider the Minimum Rainbow Subgraph problem (MRS): Given a graph G with n vertices whose edges are coloured with p colours, find a subgraph F subset of G of minimum order and with p edges such that F contains each colour exactly once. We present a polynomial time (1/2 + (1/2 + is an element of)Delta)-approximation algorithm for the MRS problem for an arbitrary small positive c. This improves the previously best known approximation ratio of 5/6 Delta. We also prove the MRS problem to be NP-hard and APX-hard for graphs with maximum degree 2. Finally we present an algorithm to find an optimal solution in running time 0(2((P+2P log2 Delta))n(0(1))). (C) 2010 Elsevier B.V. All rights reserved.
approximation rainbow subgraph algorithm np-hard