### 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(n^{O(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 - Jan 1 2014 |

### Fingerprint

### Keywords

- Approximation algorithms
- Combinatorial problems
- Minimum rainbow subgraph

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)