## 5 Parameterization by Number of Vertex Deletions
### Degree and Color-Degree
Hence, if an instance contains more vertices, then it has a colorful packing of size at least \(\ell\), which implies that it is a yes-instance. \(\square\)  
Using Lemma 6, we obtain the following theorem. **Theorem 7**. : Rainbow Subgraph _admits a problem kernel with at most \(2\Delta\cdot(\Delta+1)\cdot\Delta_{C}\cdot\ell^{2}\) vertices that can be computed in \(O(m^{2}+mn)\) time._  
**Proof. ** The kernelization algorithm exhaustively applies Rules 1 to 5 and then checks whether the instance contains more than \(2\Delta\cdot(\Delta+1)\cdot\Delta_{C}\cdot\ell^{2}\) vertices. If this is the case, then the algorithm answers \"yes\" (or reduces to a yes-instance of size one) which is correct by Lemma 6 or the instance has bounded size. It remains to show the running time of the algorithm. Each rule removes at least one edge or, in the case of Rule 5, immediately triggers a rule that removes at least one edge. Hence the rules are applied at most \(m\) times. Moreover, the applicability of each rulecan be tested in \(O(m+n)\) time, which can be seen as follows. Herein, we only focus on the time needed to test the condition of the rules; the modifications can be clearly performed in linear time. For Rule 1, one needs only to count the number of occurrences of an edge color, which can be done by visiting each edge and using an array of size \(p\) to count the occurrences. For Rule 2, one must first determine the set of obligatory vertices in \(O(m+n)\) time by comparing the number of incident edges for each color to the previously computed total number of edges with this color. Then, visiting each edge of \(G\), one can check in constant time whether both endpoints are obligatory. Rule 3 can clearly be performed in linear time by computing the connected components of \(G\). Rule 4 can be performed in linear time by checking for each obligatory vertex whether it has degree at least two and only obligatory neighbors. Finally, Rule 5 can be performed in linear time as follows. First, the set of obligatory vertices with only obligatory neighbors is already computed by the algorithm for Rule 4. Then, one can remove in linear time all edges that do not have at least one endpoint that is obligatory and has only obligatory neighbors. In the remaining graph, compute in linear time a matching of size two. This matching fulfills the requirements of Rule 5; if there is no such matching, then Rule 5 does not apply. Altogether, the running time of the kernelization algorithm is \(O(m^{2}+mn)\). We now consider parameterization by \((\Delta_{C},\ell)\) (recall that the color degree \(\Delta_{C}\) can be much smaller than \(\Delta\)). First, by performing the following additional data reduction rule, we can use the kernelization result for \((\Delta,\ell)\) to obtain a polynomial problem kernel for \((\Delta_{C},\ell)\). **Rule 6**. : _If \(G\) contains a vertex \(v\) such that at least \(\ell+2\) edges incident with \(v\) have the same color \(c\), then delete an arbitrary one of these edges._  
Proof of correctness. : Clearly, we cannot transform a no-instance into a yes-instance, since the color \(c\) remains in the graph after application of the rule. If \((G,\chi)\) is a yes-instance, then there is an order-\((n-\ell)\) rainbow cover of \(G\) that contains at least two vertices that are in \(G\) connected to \(v\) by an edge with color \(c\). Hence, removing at most one of these two edges does not destroy the rainbow cover. Rule 6 can be exhaustively performed in linear time: For each vertex \(v\), scan through its adjacency list, counting the number of incident edges of each color in an array of size \(p\). When encountering an edge whose color counter is \(\ell+2\), immediately delete the edge; otherwise increment the counter. Afterwards, reset the array to contain only zero entries; this can be done in \(O(\deg(v))\) time by storing a list of edge colors that are incident with \(v\) (all other entries of the array have the value zero, so only these counters have to be reset).