In Kratsch, D. & Todinca, I., editors, *Proc. of Graph-Theoretic Concepts in Computer Science (WG 2014)*, volume 8747, of *Lect Notes Comput Sci*, pages 287–298, 2014.

doi abstract bibtex

doi abstract bibtex

The NP-hard Rainbow Subgraph problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of Rainbow Subgraph for paths, trees, and general graphs. We show, for example, APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. Moreover, we show that Rainbow Subgraph is W[1]-hard with respect to the parameter k and also with respect to the dual parameter l := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomialsize problem kernel for the combined parameter l and "maximum number of colors incident with any vertex".

@InProceedings{hueffner14parameterized, author = {Falk H{\"{u}}ffner and Christian Komusiewicz and Rolf Niedermeier and Martin R{\"{o}}tzschke}, title = {The Parameterized Complexity of the Rainbow Subgraph Problem}, booktitle = {Proc. of Graph-Theoretic Concepts in Computer Science ({WG} 2014)}, year = {2014}, editor = {Dieter Kratsch and Ioan Todinca}, volume = {8747}, series = lncs, pages = {287--298}, publisher = Springer, abstract = {The NP-hard Rainbow Subgraph problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of Rainbow Subgraph for paths, trees, and general graphs. We show, for example, APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. Moreover, we show that Rainbow Subgraph is W[1]-hard with respect to the parameter k and also with respect to the dual parameter l := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomialsize problem kernel for the combined parameter l and "maximum number of colors incident with any vertex".}, comment = {brauche ich nur, um zu verdeutlichen, dass der Name Rainbow Subgraph problem (ZODIAC) schon weg ist}, doi = {10.1007/978-3-319-12340-0_24}, keywords = {rainbow subgraph problem; edge colored graph;}, owner = {Sebastian}, timestamp = {2017.03.28}, }

Downloads: 0