Better lower and upper bounds for the minimum rainbow subgraph problem

Alexandru Popa

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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
Volume543
Issue numberC
DOIs
Publication statusPublished - 2014
Externally publishedYes

Fingerprint

Upper and Lower Bounds
Subgraph
Color
Approximation algorithms
Bioinformatics
LP Rounding
Maximum Degree
Undirected Graph
Approximation Algorithms
Approximation
Graph in graph theory

Keywords

  • Approximation algorithms
  • Combinatorial problems
  • Minimum rainbow subgraph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Better lower and upper bounds for the minimum rainbow subgraph problem. / Popa, Alexandru.

In: Theoretical Computer Science, Vol. 543, No. C, 2014, p. 1-8.

Research output: Contribution to journalArticle

@article{98a113c67c4e4a84986a13c75f40c5f1,
title = "Better lower and upper bounds for the minimum rainbow subgraph problem",
abstract = "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)).",
keywords = "Approximation algorithms, Combinatorial problems, Minimum rainbow subgraph",
author = "Alexandru Popa",
year = "2014",
doi = "10.1016/j.tcs.2014.05.008",
language = "English",
volume = "543",
pages = "1--8",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "C",

}

TY - JOUR

T1 - Better lower and upper bounds for the minimum rainbow subgraph problem

AU - Popa, Alexandru

PY - 2014

Y1 - 2014

N2 - 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)).

AB - 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)).

KW - Approximation algorithms

KW - Combinatorial problems

KW - Minimum rainbow subgraph

UR - http://www.scopus.com/inward/record.url?scp=84909600118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84909600118&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2014.05.008

DO - 10.1016/j.tcs.2014.05.008

M3 - Article

VL - 543

SP - 1

EP - 8

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - C

ER -