The Parameterized Complexity of the Rainbow Subgraph Problem†

Algorithms

Falk Hﳿner²  Christian Komusiewicz¹  Rolf Niedermeier²  Martin Rötzschke² 

[1] Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany;

关键词: APX-hardness;    multivariate complexity analysis;    fixed-parameter tractability;    parameterized hardness;    problem kernel;    haplotyping;   

DOI  :  10.3390/a8010060

来源: mdpi

【 摘 要 】

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 that RAINBOW SUBGRAPH is W[1]-hard with respect to the parameter k and also with respect to the dual parameter ℓ := n − k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter ℓ and “maximum number of colors incident with any vertex”. Additionally, we show APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice.

【 授权许可】

CC BY   
© 2015 by the authors; licensee MDPI, Basel, Switzerland