## 4 Parameterization by Number of Colors
### Degree-Bounded Graphs
To retrieve the actual solution family, we search for some \(U^{\prime}\subseteq U\) such that \(Q^{\lceil\log_{2}|U|\rceil}[U^{\prime}]+Q^{\lceil\log_{2}|U|\rceil}[U\setminus U ^{\prime}]=Q^{\lceil\log_{2}|U|\rceil}[U]\). We repeat this step for \(U^{\prime}\) and \(U\setminus U^{\prime}\) recursively, until we obtain subsets of \(U\) that have a 1-cover. The union of those 1-covers is the solution family. We now bound the running time. The initial mapping \(Q\) can be constructed within \(O(|U|\cdot|\mathcal{C}|)=O(2^{|U|}|U|)\) time. Next, we compute \(\lceil\log_{2}|U|\rceil\) convolutions of \(Q\). Applying Lemma 2 with \(f=g=Q\), each convolution can be computed in \(O(2^{|U|}|U|^{3}\cdot W\log^{2}(|U|\cdot W))\) time. Retrieving the solution family takes \(O(2^{|U|}|U|)\) time, so we obtain an overall running time of \(O(2^{|U|}\cdot|U|^{3}\cdot W\log|U|\log^{2}(|U|\cdot W))\). **Lemma 4**. : Minimum-Weight Set Cover _can be solved in \(O(|U|\cdot|\mathcal{C}|+2^{|U|}|U|^{3}\cdot W\log|U|\log^{2}(|U|\cdot W))\) time._  
**Proof. ** We can reduce an instance \((\mathcal{C},w)\) of Minimum-Weight Set Cover to an instance \((\bar{\mathcal{C}},\bar{w})\) of Minimum-Weight Exact Cover by adding the power set of each set, that is, \(\bar{\mathcal{C}}:=\bigcup_{C_{i}\in\mathcal{C}}\mathcal{P}(C_{i})\) and \(\bar{w}:=C\mapsto\min_{C_{i}\in\mathcal{C}}w(C_{i})\). However, applying this reduction explicitly would incur the \(2^{|U|}|\mathcal{C}|\) term we aim to avoid. Thus, we directly calculate from \((\mathcal{C},w)\) the table \(Q^{0}\) that would result from the input \((\bar{\mathcal{C}},\bar{w})\) in the Minimum-Weight Exact Cover algorithm from Lemma 3. Recall that \(Q^{0}[U^{\prime}]\) is the minimum weight of a \(1\)-cover for \(U^{\prime}\) if such a cover exists and \(Q^{0}[U^{\prime}]=\infty\) otherwise; here, a \(1\)-cover is a set \(C_{i}\in\mathcal{C}\) with \(U^{\prime}\subseteq C_{i}\). We can fill out \(Q^{0}\) by first setting \(Q^{0}[C_{i}]:=w(C_{i})\) for \(C_{i}\in\mathcal{C}\) and then iterating over each set \(U^{\prime}\subseteq U\) in decreasing order of size, updating an entry \(Q^{0}[U^{\prime}]\) by  
\[Q^{0}[U^{\prime}]\leftarrow\min(Q^{0}[U^{\prime}],\min_{u\in U}Q^{0}[U^{\prime} \cup\{u\}]). \tag{6}\]Afterwards, we continue with the algorithm as before. Inserting the values of each \(C_{i}\in\mathcal{C}\) takes \(O(|U|\cdot|\mathcal{C}|)\) time, the running time for filling in the remaining values of \(Q^{0}\) is dominated by the running time of the remaining part of the algorithm. To retrieve the actual solution, we need to find for each set in the Minimum-Weight Exact Cover solution a minimum-weight set in \(\mathcal{C}\) that is its superset. This can be done naively in \(O(|U|\cdot|\mathcal{C}|\cdot|U|)\) time, which is also covered by the running time bound of the lemma, since \(|\mathcal{C}|\leq 2^{|U|}\). **Theorem 4**: _Let \((G,\chi)\) be an instance of Minimum Rainbow Subgraph with \(p\) colors and maximum vertex degree \(\Delta\). An optimal solution can be computed in \(((4\Delta-4)^{k}+2^{k\Delta/2})\cdot n^{O(1)}\) time._  
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. Again by Lemma 1, we can perform the enumeration step in \(O((4\Delta-4)^{k^{\prime}}\cdot n^{2})\) time. Then we reduce to a Minimum-Weight Set Cover instance with \(U=\{1,\ldots,p\}\). By Lemma 4, this Minimum-Weight Set Cover instance can be solved in \(2^{p}\cdot n^{O(1)}\) time. Since \(k^{\prime}\leq k\) and \(p\leq k\Delta/2\) (Equation (2)), we obtain the claimed bound.