## 4 Parameterization by Number of Colors
### Degree-Bounded Graphs
Minimum-Weight Exact Cover  
**Instance:** A set family \(\mathcal{C}=\{C_{1},\ldots,C_{m}\}\) with weight function \(w:\mathcal{C}\to\{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 exactly one set in \(\mathcal{S}\). [PERSON] _et al._[18] (Theorem 4) have given an inclusion-exclusion algorithm for the problem (although stated for the maximization version and \(k\)-covers). Their result hides some lower-order factors in the running time bound. We give an alternative algorithm and also show the lower-order factors. **Lemma 3**. : Minimum-Weight Exact Cover _can be solved in \(O(2^{|U|}\cdot|U|^{3}\cdot W\log|U|\log^{2}(|U|\cdot W))\) time._  
**Proof. ** We define an \(x\)_-cover_ of a subset \(U^{\prime}\subseteq U\) to be a minimum-weight subfamily \(\mathcal{C}^{\prime}\subseteq\mathcal{C}\) containing at most \(x\) sets such that each element of \(U^{\prime}\) occurs in exactly one set of \(\mathcal{C}^{\prime}\) and \(\bigcup_{C_{i}\in\mathcal{C}^{\prime}}C_{i}=U^{\prime}\). In these terms, Minimum-Weight Exact Cover is to find a \(|U|\)-cover for \(U\) (since every exact cover contains at most \(|U|\) sets). Consider a mapping \(Q:2^{U}\to\{0,\ldots,W\}\) and let initially \(Q[C_{i}]=w(C_{i})\) for \(C_{i}\in\mathcal{C}\) and \(Q[U^{\prime}]=\infty\) for the remaining \(U^{\prime}\subseteq U\). Now let \(Q^{x}\) denote the mapping resulting from \(x\) consecutive convolutions of \(Q\), that is, \(Q^{0}=Q\) and \(Q^{x+1}\) is the convolution of \(Q^{x}\). We prove by induction on \(x\) that for all \(U^{\prime}\subseteq U\) and all \(x\geq 0\), \(Q^{x}[U^{\prime}]\) is the minimum weight of a \(2^{x}\)-cover for \(U^{\prime}\) if such a cover exists and \(Q^{x}[U^{\prime}]=\infty\) otherwise. This implies in particular that \(Q^{\lceil\log_{2}|U|\rceil}[U]\) is the weight of an optimal solution to \(\mathcal{C}\), if a solution exists. Clearly the mapping \(Q^{0}=Q\) meets the claim. Now assume that \(Q^{x-1}[U^{\prime}]\) is the minimum weight of a \(2^{x-1}\)-cover for \(U^{\prime}\subseteq U\) if such a cover exists, and \(Q^{x-1}[U^{\prime}]=\infty\) otherwise. Now let \(\mathcal{C}^{\prime}\) be a \(2^{x}\)-cover for some \(U^{\prime}\subseteq U\). Let \(\mathcal{C}_{\alpha},\mathcal{C}_{\beta}\subseteq\mathcal{C}^{\prime}\) be disjoint subfamilies such that \(\mathcal{C}_{\alpha}\cup\mathcal{C}_{\beta}=\mathcal{C}^{\prime}\), \(|\mathcal{C}_{\alpha}|\leq 2^{x-1}\), and \(|\mathcal{C}_{\beta}|\leq 2^{x-1}\). (If \(|\mathcal{C}^{\prime}|=1\), then \(\mathcal{C}_{\alpha}=\mathcal{C}^{\prime}\) and \(\mathcal{C}_{\beta}=\emptyset\)). Let \(U_{\alpha}:=\bigcup_{C_{i}\in\mathcal{C}_{\alpha}}C_{i}\) and \(U_{\beta}:=\bigcup_{C_{i}\in\mathcal{C}_{\beta}}C_{i}\). Now \(\mathcal{C}_{\alpha}\) is a \(2^{x-1}\)-cover for \(U_{\alpha}\): it covers each element of \(U_{\alpha}\) exactly once, and if there was an exact cover with lower weight, we could combine it with \(\mathcal{C}_{\beta}\) to get an exact cover for \(\bigcup_{C_{i}\in\mathcal{C}^{\prime}}C_{i}\) with lower weight than \(\mathcal{C}^{\prime}\), contradicting that \(\mathcal{C}^{\prime}\) is a \(2^{x}\)-cover. The same holds for \(\mathcal{C}_{\beta}\). Hence, \(Q^{x-1}[U_{\alpha}]=w(\mathcal{C}_{\alpha})\) and \(Q^{x-1}[U_{\beta}]=w(\mathcal{C}_{\beta})\), therefore \(w(\mathcal{C}^{\prime})=Q[U_{\alpha}]+Q[U_{\beta}]\), and due to the minimality of \(w(\mathcal{C}^{\prime})\) we obtain (by convolution) \(Q^{x}[U^{\prime}]=\min_{U^{\prime\prime}\subseteq U^{\prime}}(Q[U^{\prime \prime}]+Q[U^{\prime}\setminus U^{\prime\prime}])=w(\mathcal{C}^{\prime})\). So \(Q^{x}[U^{\prime}]\) is the weight of a \(2^{x}\)-cover for \(U^{\prime}\). If no \(2^{x}\)-cover for \(U^{\prime}\) exists, then there is no \(U^{\prime\prime}\subseteq U^{\prime}\) such that \(Q^{x-1}[U^{\prime\prime}]\
eq\infty\) and \(Q^{x-1}[U^{\prime}\setminus U^{\prime\prime}]\
eq\infty\), hence \(Q^{x}[U^{\prime}]=\infty\).