Approximating the rainbow - Better lower and upper bounds

Alexandru Popa

Research output: Contribution to journalConference article

2 Citations (Scopus)


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 where each edge is coloured 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 max (√2p, min q (q + Δ/e pq2/Δn))- approximation algorithm using LP rounding, where Δ is the maximum degree in the input graph. In particular, this is a max (√2n, √2Δ lnΔ)-approximation algorithm. 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 ⊆ TIME(n O(loglogn)).

Original languageEnglish
Pages (from-to)193-203
Number of pages11
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7434 LNCS
Publication statusPublished - Sep 6 2012
Event18th Annual International Computing and Combinatorics Conference, COCOON 2012 - Sydney, NSW, Australia
Duration: Aug 20 2012Aug 22 2012


ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this