## 5 Parameterization by Number of Vertex Deletions
### Degree and Color-Degree
Finally, the rule does not change the value of \(\ell\), so each vertex needs to be visited only once. After exhaustive application of the rule, the maximum degree \(\Delta\) of \(G\) is at most \(\Delta_{C}\cdot(\ell+1)\). In combination with Theorem 7, this immediately implies the following. **Theorem 8**. : Rainbow Subgraph _has a problem kernel with at most \(2(\Delta_{C}+1)^{3}\ell^{2}(\ell+1)^{2}\) vertices that can be computed in \(O(m^{2}+mn)\) time._  
Finally, we describe a simple branching for the parameter \((\Delta_{C},\ell)\). Herein, _deleting a vertex_ means to remove it from \(G\) and to decrease \(\ell\) by one; thus, a deleted vertex is _not_ part of a rainbow cover of order \(k\) of the original instance. **Branching Rule 1**. : _If \(G\) contains a non-obligatory vertex \(u\), then branch into the following cases. First, recursively solve the instance obtained from deleting \(u\) from \(G\). Then, for each color \(c\) that is incident with \(u\) pick an edge \(\{v,w\}\) with color \(c\). If \(v\) (\(w\)) is non-obligatory, then recursively solve the instance obtained from deleting \(v\) (\(w\))._  
**Proof of correctness. ** We show that  
\[(G,\chi)\]  
is a yes-instance  
\[\Leftrightarrow\]  
one of the created instances is a yes-instance. (15)  
\"\(\Rightarrow\)\": Consider some maximum-cardinality set \(S\) such that \(|S|\geq\ell\) and \(G-S\) is a rainbow cover of \(G\). If \(S\) contains any of the vertices \(v\) and \(w\) considered in the second part of the branching, then the claim holds. Otherwise, for each color \(c\) that is incident with \(u\), there is an edge in \(G-S\) that has color \(c\). In this case, we can assume \(u\in S\) since \(S\) has maximum cardinality, so the claim also holds in this case. \"\(\Leftarrow\)\": Consider any instance \((G^{\prime},\chi^{\prime})\) created during the branching and let \(S\) denote a set of at least \(\ell-1\) vertices such that \(G^{\prime}-S\) is a rainbow cover of \(G^{\prime}\). Let \(v\) denote the vertex that is in \(G^{\prime}\) but not in \(G\). Since \(v\) is non-obligatory, all colors in \(G\) are also present in \(G^{\prime}\). Hence, \(G^{\prime}-(S\cup\{v\})\) is also a rainbow cover of \(G\). Hence, \((G,\chi)\) is also a yes-instance. \(\qed\)  
Note that the parameter \(\ell\) decreases by one in each branch. Exhaustively applying Branching Rule 1 until either every vertex is obligatory or \(\ell\leq 0\) yields an algorithm with the following running time. **Theorem 9**. : Rainbow Subgraph _can be solved in \(O((2\Delta_{C}+1)^{\ell}\cdot(n+m))\) time._  
**Proof. ** The algorithm exhaustively applies Branching Rule 1 until either every vertex is obligatory or \(\ell\leq 0\). By the correctness of Branching Rule 1 the original instance is a yes-instance if and only if at least one of the created instances is a yes-instance. If \(\ell=0\), then the instance is a trivial yes-instance and the algorithm may correctly answer \"yes\". Otherwise, \(\ell>0\) but all vertices are obligatory. In this case, the instance is a trivial no-instance and the algorithm simply leaves the current branch. If the answer for none of the created instances is \"yes\", then the algorithm correctly answers \"no\". It remains to show the running time bound. The search tree created by Branching Rule 1 has depth \(\ell\) and maximum degree \((2\Delta_{C}+1)\), hence it has size \(O((2\Delta_{C}+1)^{\ell})\). In each node of the instance, we have to test for the applicability of Branching Rule 1, which can be performed in linear time. \(\qed\)