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 language | English |
|---|---|
| Pages (from-to) | 1-8 |
| Number of pages | 8 |
| Journal | Theoretical Computer Science |
| Volume | 543 |
| Issue number | C |
| DOIs | |
| Publication status | Published - 2014 |
| Externally published | Yes |
Fingerprint
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 journal › Article
}
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 -