## 5 Parameterization by Number of Vertex Deletions
### Hardness on Trees  
In contrast to the parameter \(k\), for which Rainbow Subgraph becomes fixed-parameter tractable on trees, we observe W[1]-hardness for parameter \(\ell\) even on very restricted input trees. To achieve this hardness result, we describe a parameterized reduction from the following restricted variant of Independent Set. Independent Set with Perfect Matching  
**Instance:** An undirected graph \(G=(V,E)\) with a perfect matching \(M\subseteq E\), and an integer \(\kappa\geq 0\). **Question:** Is there a vertex set \(S\subseteq V\) with \(|S|=\kappa\) such that \(G[S]\) has no edges? First, we show the parameterized hardness of Independent Set with Perfect Matching. **Lemma 5**: _Independent Set with Perfect Matching is W[1]-hard with respect to the parameter \(\kappa\)  
**Proof. ** To show the claim, we give a parameterized reduction from the classic W[1]-hard Independent Set problem [12] which differs from Independent Set with Perfect Matching only in the fact that the input graph \(G\) may not have a perfect matching. Given an input instance \((G=(V,E),\kappa)\) of Independent Set, the reduction works as follows. Compute a maximum-size matching \(M\) of \(G\) in polynomial time. If \(M\) is perfect, then \((G,M,\kappa)\) is an equivalent instance of Independent Set with Perfect Matching. Otherwise, build a graph \(G^{*}\) that contains for each vertex \(v\in V\) two adjacent vertices \(v_{1}\) and \(v_{2}\) and then add for each pair of vertices \(u_{i}\) and \(v_{j}\) in \(G^{*}\) with \(i,j\in\{1,2\}\) the edge \(\{u_{i},v_{j}\}\) if \(u\) and \(v\) are adjacent in \(G\). If \(G\) has an independent set of size \(\kappa\), then \(G^{*}\) has one since the subgraph \(G^{*}[\{v_{1}\mid v\in V\}]\) is isomorphic to \(G\). If \(G^{*}\) has an independent set \(S\) of size \(\kappa\), then so does \(G\): Since \(v_{1}\) and \(v_{2}\) are adjacent, the independent set can contain at most one of them and thus, without loss of generality it contains \(v_{1}\). Hence, \(G^{*}[S]\) is a subgraph of \(G^{*}[\{v_{1}\mid v\in V\}]\) which is isomorphic to \(G\). Clearly, \(G^{*}\) has a perfect matching \(M\) consisting of the edges \(\{v_{1},v_{2}\}\) for \(v\in V\). Thus, \((G^{*},M,\kappa)\) is an equivalent instance of Independent Set with Perfect Matching. The reduction runs in polynomial time and the parameter remains the same. Thus, it is a parameterized reduction. \(\Box\)  
Now we can show the W[1]-hardness of Rainbow Subgraph for the parameter \(\ell\). In our reduction, the existence of a perfect matching in the Independent Set with Perfect Matching instance allows us to construct instances in which every edge color occurs at most twice. **Theorem 6**. : Rainbow Subgraph _is W[1]-hard with respect to the dual parameter \(\ell\) even when the input is a tree of height three and every color occurs at most twice._  
**Proof. ** Let \((G,M,\kappa)\) be an instance of Independent Set with Perfect Matching (which is W[1]-hard with respect to \(\kappa\) by Lemma 5). We construct a Minimum Rainbow Subgraph instance \((G^{\prime}=(V^{\prime},E^{\prime}),\chi)\) as follows; an illustration is given in Figure 2. First, set \(V^{\prime}:=V\). Then do the following for each edge \(\{u,v\}\in E\). Add four vertices \(u^{1}_{v},u^{2}_{v},v^{1}_{u},v^{2}_{u}\). Make \(u^{1}_{v}\) and \(u^{2}_{v}\) adjacent and color the edge with some unique color. Analogously, make \(v^{1}_{u}\) and \(v^{2}_{u}\) adjacent and color the edge with some other unique color. Now, add an edge between \(u\) and \(u^{1}_{v}\) and an edge between \(v\) and \(v^{1}_{u}\). Color both edges with the new color \(c_{\{u,v\}}\). Finally, add another vertex \(v^{*}\) and make \(v^{*}\) adjacent to all vertices of \(V\). To color the edges between \(v^{*}\) and \(V\), we use the perfect matching \(M\). For each edge \(\{u,v\}\) of \(M\), we color the edges \(\{v^{*},u\}\) and \(\{v^{*},v\}\) with the same new color \(c^{M}_{\{u,v\}}\).