## 4 Parameterization by Number of Colors
### Hardness on Bipartite Graphs  
A graph \(G\) is called \(d\)_-degenerate_ if every subgraph of \(G\) has a vertex of degree at most \(d\). We can show that even on \(2\)-degenerate bipartite graphs, the decision problem Rainbow Subgraph is W[1]-hard for parameter \(p\) (and thus also for parameter \(k\)) by a parameterized reduction from the Multicolored Clique problem.  
**Theorem 2**.: Minimum Rainbow Subgraph _is W[1]-hard with respect to the number of colors \(p\), even if the input graph is \(2\)-degenerate and bipartite._  
Proof.: We give a parameterized reduction from the following well-known problem:  
Multicolored Clique  
**Instance:** An undirected graph \(G=(V,E)\) with proper vertex coloring \(\chi_{V}:V\rightarrow\{1,\ldots,p_{V}\}\).  
**Question:** Does \(G\) have a clique of order \(p_{V}\)?  
Here, _proper_ means that \(\{u,v\}\in E\Rightarrow\chi_{V}(u)\
eq\chi_{V}(v)\). Multicolored Clique is W[1]-complete with respect to parameter \(p_{V}\)[16].  
Let \((G=(V,E),\chi_{V})\) be an instance of Multicolored Clique. We construct a bipartite edge-colored graph \(G^{\prime}\) with vertex set initialized with \(V\) as follows. First, for every edge \(\{u,v\}\) of \(G\) add to \(G^{\prime}\) a path of length two between \(u\) and \(v\) where the middle vertex of this path is a new vertex \(\omega_{\{u,v\}}\). Call the union of all middle vertices \(V_{E}\). Then, for each pair of vertex colors \(i\) and \(j\) of \(G\) create two new edge colors \(c_{i,j}\) and \(c_{j,i}\). For each edge \(\{u,v\}\) of \(G\) where \(\chi_{V}(u)=i\) and \(\chi_{V}(v)=j\), color the edge \(\{u,\omega_{\{u,v\}}\}\) with color \(c_{i,j}\) and the edge \(\{v,\omega_{\{u,v\}}\}\) with color \(c_{j,i}\). This completes the construction of \(G^{\prime}\). Note that \(G^{\prime}\) is 2-degenerate and that it has \(2\binom{p_{V}}{2}\) edge colors overall. We now show the equivalence of the instances.  
\[G\]  
has a clique of size  
\[p_{V}\Leftrightarrow G^{\prime}\]  
has a rainbow subgraph with at most  
\[p_{V}+\binom{p_{V}}{2}\]  
vertices. (5)  
\"\(\Rightarrow\)\": Let \(S\) be a clique of size \(p_{V}\) in \(G\). Since \(\chi_{V}\) is a proper coloring of \(G\), the vertices in \(S\) have \(p_{V}\) pairwise different colors. Hence, the subgraph of \(G^{\prime}\) that is induced by \(S\cup\{\omega_{\{u,v\}}\mid\{u,v\}\subseteq S\}\) has \(2\binom{p_{V}}{2}\) edges which have pairwise different colors.  
\"\(\Leftarrow\)\": Let \(S^{\prime}\) be the vertex set of a rainbow subgraph with at most \(p_{V}+\binom{p_{V}}{2}\) vertices in \(G^{\prime}\). We can assume that \(S^{\prime}\) has exactly \(p_{V}+\binom{p_{V}}{2}\) vertices since adding isolated vertices does not destroy the property of being a solution. Since in particular every color \(c_{i,1}\) and \(c_{1,i}\) is covered, \(S^{\prime}\) has at least one vertex from \(V\) for each color \(i\), together at least \(p_{v}\) vertices. Moreover, \(S^{\prime}\) has at least \(\binom{p_{V}}{2}\) vertices from \(V_{E}\): we need at least \(2\binom{p_{V}}{2}\) edges to collect all colors, each edge contains exactly one vertex from \(V_{E}\), and each vertex in \(V_{E}\) occurs in at most two edges. Thus, there are exactly \(p_{v}\) vertices from \(V\) and exactly \(\binom{p_{V}}{2}\) vertices from \(V_{E}\) in \(S^{\prime}\). In order to cover the \(2\binom{p_{V}}{2}\) colors, each vertex in \(V_{E}\) needs to have degree two in \(G^{\prime}[S^{\prime}]\); since such a vertex corresponds to an edge in \(G\), we have \(\binom{p_{V}}{2}\) edges in \(G[V\cap S^{\prime}]\), and we have a clique of size \(p_{V}\).