## 6 Capacitated Vertex Cover and Dominating Set
Abusing notation, for \(A,B\subseteq V(G)\), we simply write \(H[A,B]\) to denote the graph \(H[\{w_{u}:u\in A\}\cup\{w_{u}^{i}:u\in B,1\leq i\leq c(u)\}]\). As shown in Proposition 2, the capacitated dominating set \((X,\beta_{X})\) (resp. \((Y,\beta_{Y})\)) forms a matching \(M_{X}\) (resp. \(M_{Y}\)) saturating \(\{w_{u}:u\in V(G)\setminus X\}\) (resp., \(\{w_{u}:u\in V(G)\setminus Y\}\)) in \(H[V(G)\setminus X,X]\) (resp., \(H[V(G)\setminus Y,Y]\)) and vice versa. As \(v\in X\), for \(u\in\beta_{X}^{-1}(v)\), \(M_{X}\) has an edge \(\{w_{u},w_{v}^{i^{*}}\}\) for some \(i^{*}\). Moreover, as \(v\
ot\in Y\), \(w_{v}^{i}\) has no incident edge in \(M_{Y}\) for any \(i\). Thus, the component of \(M_{X}\triangle M_{Y}\) containing \(w_{v}^{i^{*}}\) is an alternating path \(P\) whose one end vertex is \(w_{v}^{i^{*}}\). Suppose that the other end vertex of \(P\) belongs to \(V^{\prime}\). Let \(w_{u^{*}}\) be the end vertex of \(P\) other than \(w_{v}^{i^{*}}\). In this case, we have \(u^{*}\
otin X\) as in Figure 1(a). Then, \((M_{X}\setminus E(P))\cup(M_{Y}\cap E(P))\) is a matching in \(H[V(G)\setminus(X\cup\{u^{*}\}),X\cup\{u^{*}\}]\) saturating \(\{w_{x}:x\in V(G)\setminus(X\cup\{u^{*}\})\}\). Suppose otherwise that the other end vertex of \(P\) belongs to \(V\). Let \(w_{u^{*}}^{i^{*}}\) be the end vertex of \(P\) other than \(w_{v}^{i^{*}}\) as in Figure 1(b). Then, \((M_{X}\setminus E(P))\cup(M_{Y}\cap E(P))\) is a matching in \(H[V(G)\setminus(X\cup\{u^{*}\}),X\cup\{u^{*}\}]\) saturating \(\{w_{x}:x\in V(G)\setminus(X\cup\{u^{*}\})\}\). In both cases, we have \(u^{*}\in Y\) as (a) \(w_{u^{*}}\) has no incident edge in \(M_{Y}\) or (b) \(w_{u^{*}}^{i^{*}}\) has an incident edge in \(M_{Y}\). Let \(M^{*}\) be the matching in \(H\) by applying one of the two cases (a) and (b) for all \(u\in\beta^{-1}(v)\). Then, by letting \(W^{*}=\{u^{*}\in Y:u\in\beta^{-1}(v)\}\), \(M^{*}\) saturates \(\{w_{u}:u\in V(G)\setminus((X\setminus\{v\})\cup W^{*})\}\); hence, \((X\setminus\{v\})\cup W^{*}\) dominates all the vertices of \(V(G)\) except for \(v\). Similarly, \(w_{v}\) has an incident edge in \(M_{Y}\) but no incident edge in \(M^{*}\). There is an alternating path component \(P\) in \(M^{*}\triangle M_{Y}\) whose end vertex is \(w_{v}\). Note that \(P\) has at least one edge. Note moreover that \(P\) has no vertices of \(w_{v}^{i}\) for any \(i\) as \(M^{*}\) has no edges incident to them and \(v\
ot\in Y\). By applying the same argument as above, we can define \(v^{*}\in Y\), and by letting \(W=W^{*}\cup\{v^{*}\}\), there is a matching in \(H[V(G)\setminus((X\setminus\{v\})\cup W),(X\setminus\{v\})\cup W]\) saturating \(\{w_{u}:u\in V(G)\setminus((X\setminus\{v\})\cup W)\}\). This implies that, by Proposition 2, \((X\setminus\{v\})\cup W\) is a capacitated dominating set of \((G,c)\). The above two lemmas together with Proposition 2 and Theorem 1 yield polynomial-delay algorithms on bounded-degree graphs. Theorem 4.2: _There are \(n^{\min\{q,A\}+O(1)}\)-delay enumeration algorithms for Minimal Capacitated Vertex Cover Enumeration and Minimal Capacitated Dominating Set Enumeration, where \(q=\max_{v\in V(G)}c(v)\) and \(\Delta\) is the maximum degree of \(G\)._  
Figure 2: Depiction of the matchings \(M_{X}\) (black edges) and \(M_{Y}\) (red edges) in \(H\). Similarly to Theorem 4, Minimal Capacitated Vertex Cover Enumeration is \"not so easy\" even if an input graph is 2-degenerate bipartite. Theorem 4.1: _If there is an output-polynomial time (or a polynomial-delay) algorithm for Minimal Capacitated Vertex Cover Enumeration on 2-degenerate bipartite graphs, then there is an output-polynomial time (or a polynomial-delay) algorithm for enumerating minimal transversals in hypergraphs._  
Proof: The underlying idea of the proof is analogous to Theorem 4.