## 6 Capacitated Vertex Cover and Dominating Set
From a hypergraph \(\mathcal{H}=(V,\mathcal{E})\), we first construct a bipartite graph \(G\) and a capacity function \(c\colon V(G)\to\mathbb{N}\) and then transform them into a 2-degenerate bipartite graph \(G^{\prime}\) and a function \(c^{\prime}\colon V(G^{\prime})\to\mathbb{N}\). Notice that our reduction from the minimal transversal enumeration to Minimal Capacitated Vertex Cover Enumeration is almost the same. We start with the incident bipartite graph of \(\mathcal{H}\) (see Theorem 4 for details). For each \(w_{e}\in V_{\mathcal{E}}\), we add a pendant vertex \(w_{e}^{\prime}\), and the obtained graph is denoted by \(G\). See Figure 2(a) for an illustration. We define the capacity function \(c\colon V(G)\to\mathbb{N}\) as  
\[c(v)= \begin{cases}d(v)&\text{if }v\in\ V\\ d(v)-1&\text{if }v\in V_{\mathcal{E}}\\ 0&\text{otherwise}.\end{cases} \]  
Here, \(d(v)\) is the degree of \(v\) in \(G\). Let \(C\) be an arbitrary minimal capacitated vertex cover of \((G,c)\) and let \(\alpha\colon E(G)\to\mathcal{C}\) be a function such that \((C,\alpha)\) is a capacitated vertex cover of \((G,c)\). As \(c(w_{e}^{\prime})=0\) for \(e\in\mathcal{E}\), we have \(V_{\mathcal{E}}\subseteq C\). Moreover, \(\alpha\) maps the incident edge of \(w_{e}^{\prime}\) to \(w_{e}\) for each \(e\in\mathcal{E}\). Since \(c(w_{e})=d(v)-1\), \(\alpha\) maps at least one edge incident to \(w_{e}\) to a vertex \(v\) in \(C\cap V\). Applying the construction of \(G\), such a vertex \(v\) is contained in the hyperedge \(e\). This implies that \(S=C\cap V\) is a transversal of \(\mathcal{H}\). The remaining part of this proof is analogous to that in Theorem 4. We now transform \((G,c)\) into \((G^{\prime},c^{\prime})\). The construction of \(G^{\prime}\) is again analogous to that in Theorem 4. For each \(e\in\mathcal{E}\) with \(|e|=d\), we replace \(w_{e}\) and \(w_{e}^{\prime}\) with a path \(P_{e}=(p_{1}^{2},\ldots,p_{2d+1}^{e})\) and \(2d+1\) pendant vertices in the same fashion as in Theorem 4. The obtained graph is denoted by \(G^{\prime}\). We define the capacity function \(c^{\prime}\colon V(G^{\prime})\to\mathbb{N}\) as  
\[c^{\prime}(v)= \begin{cases}d^{\prime}(v)&\text{if }v\in\ V\\ d^{\prime}(v)-1&\text{if }v\in V(P_{e})\text{ for }e\in\ E\\ 0&\text{otherwise},\end{cases} \]  
where \(d^{\prime}(v)\) is the degree of \(v\) in \(G^{\prime}\). (See Figure 2(b) for an illustration.) Let \(C\) be an arbitrary minimal capacitated vertex cover of \((G^{\prime},c^{\prime})\) and let \(\alpha\colon E(G^{\prime})\to C\) be a function such that \((C,\alpha)\) is a capacitated vertex cover of \((G^{\prime},c^{\prime})\). As the capacity of the pendant vertex adjacent to each vertex \(p_{i}^{e}\) in \(V(P_{e})\) is zero, \(\alpha\) maps the edge between them to \(p_{i}^{e}\), which implies that \(V(P_{e})\subseteq C\) for all \(e\in\mathcal{E}\). Since the sum of the capacities of the vertices in \(V(P_{e})\) is exactly one less than the number of edges incident to \(V(P_{e})\), \(\alpha\) maps at least one edge to a vertex in \(V\). This allows us to simulate the correspondence between the family of minimal transversals of \(\mathcal{H}\) and the family of minimal capacitated vertex covers of \(G\).