## 4 Parameterization by Number of Colors
### Degree-Bounded Graphs  
Replacing degeneracy by the larger parameter maximum degree \(\Delta\) of \(G\) yields fixed-parameter tractability: [PERSON] and [PERSON] [4] proposed an algorithm that solves Minimum Rainbow Subgraph in \((2\Delta^{2})^{p}\cdot n^{O(1)}\) time. We show an improved bound of \(O((4\Delta-4)^{p}\cdot\Delta n^{2})\). The algorithm by [PERSON] and [PERSON] [4] works by enumerating all connected rainbow subgraphs in \(O(\Delta^{2p}\cdot np)\) time and finding a solution via dynamic programming. We also employ enumeration followed by dynamic programming, but enumerate only connected _induced_ subgraphs. For this, we use the following lemma. **Lemma 1**. : _([17], Lemma 2) Let \(G\) be a graph with maximum degree \(\Delta\) and let \(v\) be a vertex in \(G\). There are at most \((4\Delta-4)^{k}\) connected induced subgraphs of \(G\) that contain \(v\) and have order at most \(k\). Furthermore, these subgraphs can be enumerated in \(O((4\Delta-4)^{k}\cdot n)\) time._  
Minimum-Weight Set Cover  
**Instance:** A set family \(\mathcal{C}\) with weight function \(w:\mathcal{C}\rightarrow\{0,\ldots,W\}\). **Task:** Find a minimum-weight subfamily \(\mathcal{S}\subseteq\mathcal{C}\) such that each element of \(U:=\bigcup_{C_{i}\in\mathcal{C}}C_{i}\)  
occurs in at least one set in \(\mathcal{S}\). The Minimum-Weight Set Cover instance is constructed by adding a set for each enumerated induced subgraph that contains the colors covered by this subgraph and is weighted by its order. **Theorem 3**. : _Let \((G,\chi)\) be an instance of Minimum Rainbow Subgraph with \(p\) colors and maximum vertex degree \(\Delta\). An optimal solution of \((G,\chi)\) can be computed in \(O((4\Delta-4)^{p}\cdot\Delta n^{2})\) time._  
Proof. : Let \((G,\chi)\) be an instance of Minimum Rainbow Subgraph and let \(k^{\prime}\) be the maximum order of a connected component of a solution. By Lemma 1, we can enumerate in \(O((4\Delta-4)^{k^{\prime}}\cdot n^{2})\) time all connected induced subgraphs of order at most \(k^{\prime}\), and in particular all subgraphs induced by the connected components of a solution to \(G\). By interleaving the construction of the set of colors occurring in the current subgraph with the graph enumeration, we can generate the Minimum-Weight Set Cover instance in the same time bound. It is easy to see that Minimum-Weight Set Cover with \(|U|=p\) can be solved in \(O(2^{p}p|\mathcal{C}|)\) time and exponential space by dynamic programming. Since \(|\mathcal{C}|\) may be as large as \(2^{p}\), this yields a bound of \(O(4^{p}p)\). Because connected components of a solution are rainbow, we can assume \(k^{\prime}\leq p+1\) (a connected graph with \(m\) edges has at most \(m+1\) vertices) and obtain \(O((4\Delta-4)^{p+1}n^{2}+4^{p}p)\) time. For \(\Delta\geq 2\), this running time is dominated by the enumeration step, yielding the desired bound. If we parameterize by \(\Delta\) and \(k\) instead of \(\Delta\) and \(p\), the second step can dominate when \(k\) is small compared to \(p\). Thus, a faster algorithm for Minimum-Weight Set Cover is desirable. To solve the problem in \(2^{|U|}(|U|\cdot W)^{O(1)}\) time, we will employ a variant of fast subset convolution [18], using the following lemma due to [PERSON] _et al._[19]. **Lemma 2**. : _[_19_]_ _Consider a set \(U\) and two mappings \(f,g:2^{U}\to\{0,\ldots,W\}\). The mapping \((f*g):2^{U}\to\{0,\ldots,2W\}\) where for every \(U^{\prime}\subseteq U\)_  
\[(f*g)[U^{\prime}]:=\min_{U^{\prime\prime}\subseteq U^{\prime\prime}}(f[U^{ \prime\prime}]+g[U^{\prime}\setminus U^{\prime\prime}])\]  
_is called the convolution of \(f\) and \(g\) and can be computed in \(O(2^{|U|}\cdot|U|^{3}\,W\log^{2}(|U|\cdot W))\) time._  
[PERSON] _et al._[19] did not give precise running time estimates, but Lemma 2 can be derived using their Theorem 1. (Here, to avoid complicated terms, we assume a bound of \(O(N\log^{2}N)\) on the running time of integer multiplication of two \(N\)-bit numbers. Better bounds are known [20].)