## 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 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 language | English |
---|---|

Pages (from-to) | 193-203 |

Number of pages | 11 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 7434 LNCS |

DOIs | |

Publication status | Published - Sep 6 2012 |

Event | 18th Annual International Computing and Combinatorics Conference, COCOON 2012 - Sydney, NSW, Australia Duration: Aug 20 2012 → Aug 22 2012 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)