The Parameterized Complexity of the Rainbow Subgraph Problem. Hüffner, F., Komusiewicz, C., Niedermeier, R., & Rötzschke, M. 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   
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