Better lower and upper bounds for the minimum rainbow subgraph problem

Alexandru Popa

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalTheoretical Computer Science
Issue numberC
Publication statusPublished - 2014


  • Approximation algorithms
  • Combinatorial problems
  • Minimum rainbow subgraph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Better lower and upper bounds for the minimum rainbow subgraph problem'. Together they form a unique fingerprint.

Cite this