The parameterized complexity of the rainbow subgraph problem (Q1736640)

Summary: The NP-hard \textsc{Rainbow} \textsc{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 \textsc{Rainbow} \textsc{Subgraph} for paths, trees, and general graphs. We show that \textsc{Rainbow} \textsc{Subgraph} is W[1]-hard with respect to the parameter \(k\) and also with respect to the dual parameter \(\ell :=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 \(\ell\) 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.