## 3 Parameterization by Color Occurrences  
We now consider the complexity of Rainbow Subgraph parameterized by the maximum number \(q\) of color occurrences. Indeed, the value of \(q\) is bounded in some applications: For example in the graph formulation of Parsimony Haplotyping, \(q\) depends on the maximum number of ambiguous positions in a genotype, which can be assumed to be small.  
[PERSON] and [PERSON] [4] showed that Minimum Rainbow Subgraph is APX-hard for \(\Delta=2\). The instances produced by their reduction contain precisely two edges of each color, so APX-hardness even holds for \(q=2\). However, the resulting graph contains cycles and is not properly edge-colored, so the complexity on acyclic graphs and on properly edge-colored graphs (like those resulting from Parsimony Haplotyping instances) remains to be explored. We show that neither restriction is helpful, as Rainbow Subgraph is APX-hard for properly edge-colored paths with \(q=2\). This strengthens the hardness result of [PERSON] and [PERSON] [4]. For this purpose, we develop an \(L\)-reduction (see Section 2) from the following special case of Minimum Vertex Cover:  
Minimum Vertex Cover in Cubic Graphs  
**Instance:** An undirected graph \(H=(W,F)\) in which every vertex has degree three.  
**Task:** Find a minimum-cardinality vertex cover of \(G\).  
Minimum Vertex Cover in Cubic Graphs is APX-hard [15].  
**Theorem 1**.: Minimum Rainbow Subgraph _is APX-hard even when the input is a properly edge-colored path in which every color occurs at most twice._  
**Proof.** Given an instance \(H=(W=\{w_{1},\ldots,w_{n}\},F)\) of Minimum Vertex Cover in Cubic Graphs, construct an edge-colored path \(G=(V,E)\) as follows. The vertex set is \(V:=\{v_{1},\ldots,v_{16n+2}\}\). The edge set is \(E:=\{\{v_{i},v_{i+1}\}\mid 1\leq i\leq 16n+1\}\), that is, vertices with successive indices are adjacent. It remains to specify the edge colors. Herein, we use \(u^{*}\) to denote _unique_ colors, that is, if an edge is \(u^{*}\)-colored, then it receives an edge color that does not appear anywhere else in \(G\). In addition to these unique colors, introduce five colors for each vertex of \(H\), that is, for each \(w_{i}\in W\) create edge colors \(c_{i}\), \(c^{\prime}_{i}\), \(c^{\prime\prime}_{i}\),  
that, conversely, there is a solution of order at most \(p+n+1+|S^{*}|\). Thus, the differences between the solution sizes in the Minimum Vertex Cover in Cubic Graphs instance and in the Minimum Rainbow Subgraph instance are essentially the same.  
We now show that \(G^{\prime}\) has order \(p+n+1+x\), \(x\geq 0\). Since \(G^{\prime}\) is a solution it contains each edge color exactly once. Thus, \(G^{\prime}\) has exactly \(p\) edges. We now apply a series of modifications to \(G^{\  
edges of \(G\) plus their endpoints to \(\hat{G}\). Then, \(\hat{G}\) contains \(p\) edges, one for each color. The number of connected components in \(\hat{G}\) is \(1+2|S^{*}|+n-|S^{*}|\), hence, the number of vertices in \(\hat{G}\) is \(p+1+|S^{*}|+n\). Consequently, we have  
\[|V(G^{\prime})|-|V(\hat{G})| =p+1+x+n-(p+1+|S^{*}|+n)\] \[\geq|S^{\prime}|-|S^{*}|=\tau.\]  
Now an optimal solution \(G^{*}\) has at most as many vertices as \(\hat{G}\), and thus  
\[|V(G^{\prime})|-|V(G^{*})|\geq|V(G^{\prime})|-|V(\hat{G})|\geq|S^{\prime}|-|S ^{*}|=\tau\]  
which directly implies Equation (4).