Better lower and upper bounds for the minimum rainbow subgraph problem
| Autoři | |
|---|---|
| Rok publikování | 2014 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.tcs.2014.05.008 |
| Obor | Informatika |
| Klíčová slova | Approximation algorithms; Combinatorial problems; Minimum rainbow subgraph |
| Popis | 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(root 2n, root Delta(1+root ln Delta/2))-approximation algorithm using LP rounding, where A 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 c In A-approximation, unless NP subset of DTIME(n(0(loglogn))) |
| Související projekty: |