## 2 Preliminaries  
We use \(n\) and \(m\) to denote the number of vertices and edges in the input graph, respectively. The _order_ of a graph \(G\) is the number \(n\) of vertices in \(G\). We call a graph \(G^{\prime}=(V^{\prime},E^{\prime})\)_induced subgraph_ of a graph \(G=(V,E)\) if \(V^{\prime}\subseteq V\) and \(E^{\prime}=\{\{u,v\}\mid u,v\in V^{\prime}\text{ and }\{u,v\}\in E\}\). The graph induced by a vertex set \(V^{\prime}\) in \(G\) is denoted \(G[V^{\prime}]\). The degree of a vertex \(v\) is denoted \(\deg(v)\). APX is the class of optimization problems that allow polynomial-time approximation algorithms with a constant approximation factor. If a problem is APX-hard, then it cannot be approximated in polynomial time to arbitrary constant factors, unless \(\text{P}=\text{NP}\). To show that a problem is APX-hard, we can use an \(L\)_-reduction_ from a known APX-hard problem. An \(L\)-reduction from a problem \(\Pi\) to a problem \(\Pi^{\prime}\) produces from an instance \(I\) of \(\Pi\) in polynomial time an instance \(I^{\prime}\) of \(\Pi^{\prime}\) such that for some constant \(a\), \(\operatorname{OPT}(I^{\prime})<a\cdot\operatorname{OPT}(I)\); additionally, it must be possible in polynomial time to produce from a feasible solution of \(I^{\prime}\) of value \(x^{\prime}\) a feasible solution of \(I\) of value \(x\) where \(|\operatorname{OPT}(I)-x|\leq b|\operatorname{OPT}(I^{\prime})-x^{\prime}|\) for some constant \(b\) ([11], Definition 16.4). An instance of a _parameterized problem_ is a pair \((I,x)\), where \(x\) is some problem-specific parameter, typically a nonnegative integer [12; 13; 14]. A problem is called _fixed-parameter tractable_ (FPT) with respect to \(x\) if it can be solved in \(f(x)\cdot|I|^{O(1)}\) time, where \(f\) is an arbitrary computable function. A _data reduction (rule)_ is a polynomial-time self-reduction for a parameterized problem, that is, it replaces in polynomial time an instance \((I,x)\) with an instance \((I^{\prime},x^{\prime})\) such that \(I^{\prime}\) has a solution with respect to the new parameter \(x^{\prime}\) if and only if \(I\) has a solution with respect to the original parameter \(x\); we say that the rule is _correct_ when this property holds. We say that an instance is _reduced_ with respect to a reduction rule if the rule does not affect the instance. If the size of \(I^{\prime}\) depends only on some function of \(x\), we say that we have a _problem kernel_ with respect to parameter \(x\). Analogously to NP, the class W[1] captures parameterized hardness [12; 13; 14]. It is widely assumed that if a problem is W[1]-hard, then it is not fixed-parameter tractable. One can show W[1]-hardness by a _parameterized reduction_ from a known W[1]-hard problem. This is a reduction that runs in \(f(x)\cdot|I|^{O(1)}\) time for some function \(f\) and maps the parameter \(x\) to a new parameter \(x^{\prime}\) that is bounded by some function of \(x\). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Par. ** & **Paths** & **Trees** & **General Graphs** \\ \hline \(p\) & \(O^{*}(2^{p})\) (Theorem 5) & \(O^{*}(2^{p})\) (Theorem 5) & W[1]-hard (Theorem 2) \\ \(p,\Delta\) & \(\dashrightarrow\dashrightarrow\) & \(\dashrightarrow\dashrightarrow\) & \(O^{*}((4\Delta-4)^{p})\) (Theorem 3) \\ \hline \(k\) & \(O^{*}(2^{k})\) (Theorem 5 + Equation (2)) & \(O^{*}(2^{k})\) (Theorem 5 + Equation (3)) & W[1]-hard (Theorem 2 + Equation (1)) \\ \(k,\Delta\) & \(  
We will use the following simple observation several times. **Observation 1**. : _Let \(G^{\prime}=(V^{\prime},E^{\prime})\) be a solution for a Rainbow Subgraph instance with \(G=(V,E)\). If there are two vertices \(u,v\) in \(V^{\prime}\) such that \(\{u,v\}\in E\) but \(\{u,v\}\
otin E^{\prime}\), then there is a solution \(G^{\prime\prime}\) that does contain the edge \(\{u,v\}\) and has the same number of vertices._  
Observation 1 is true since replacing the edge in \(G^{\prime}\) that has the same color as \(\{u,v\}\) by \(\{u,v\}\) is a solution.