Approximating the rainbow - Better lower and upper bounds

Alexandru Popa

Research output: Contribution to journalConference articlepeer-review

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)

Fingerprint Dive into the research topics of 'Approximating the rainbow - Better lower and upper bounds'. Together they form a unique fingerprint.

Cite this