## 6 Capacitated Vertex Cover and Dominating Set  
This section is devoted to showing polynomial-delay algorithms for the capacitated variants on bounded-degree graphs. The basic idea to prove Theorems 2 and 6 is that for distinct minimal solutions \(X\) and \(Y\) and for \(v\in X\setminus Y\), there always exists a constant size (depending on \(\Delta\)) vertex set \(W\subseteq Y\) such that \((X\setminus\{v\})\cup W\) is a (not necessarily minimal) solution. For Minimal Capacitated Vertex Cover Enumeration and Minimal Capacitated Dominating Set Enumeration, we can find such a set \(W\) in bounded degree graphs as well. Let \(G\) be a graph with maximum degree \(\Delta\) and let \(c\colon V(G)\to\mathbb{N}\). Let \(q=\max_{v\in V(G)}c(v)\). Without loss of generality, we can assume that \(q\leq\Delta\). Lemma 10: _Let \(X,Y\) be distinct minimal capacitated vertex covers of \((G,c)\) and let \(v\in X\setminus Y\). Then, there is a vertex set \(W\subseteq Y\) of size at most \(q\) such that \((X\setminus\{v\})\cup W\) is a capacitated vertex cover of \((G,c)\)._  
Proof: Let \(\alpha_{X}\colon E(G)\to X\) (resp. \(\alpha_{Y}\colon E(G)\to Y\)) be a function such that \((X,\alpha_{X})\) (resp. \((Y,\alpha_{Y})\)) is a capacitated vertex cover of \((G,c)\). As \(c(v)\leq q\), \(\alpha_{X}^{-1}(v)\) contains at most \(q\) edges. For each \(e=\{v,w\}\in\alpha_{X}^{-1}(v)\), we define a vertex \(v_{e}\in Y\) and show that \((X\setminus\{v\})\cup W\) with \(W=\{v_{e}:e\in\alpha_{X}^{-1}(v)\}\) is a capacitated vertex cover of \((G,c)\). To define such a vertex \(v_{e}\) for \(e\in\alpha_{X}^{-1}(v)\), we use a similar strategy as used in Proposition 2. Let \(H\) be a bipartite graph with \(V(H)=V_{E}\cup V\) such that \(V_{E}=\{w_{e}:e\in E(G)\}\) and \(V=\{w_{u}^{i}:u\in V(G),1\leq i\leq c(u)\}\). As shown in Proposition 2, the capacitated vertex cover \((X,\alpha_{X})\) (resp. \((Y,\alpha_{Y})\)) forms a matching \(M_{X}\) (resp. \(M_{Y}\)) saturating \(V_{E}\) in \(H\) and vice versa. As \(v\in X\setminus Y\), there is a vertex \(w_{v}^{i}\) that is matched in \(M_{X}\) but not matched in \(M_{Y}\). Since both \(M_{X}\) and \(M_{Y}\) are maximum matches in \(H\), there is an alternating path \(P\) between \(w_{v}^{j}\) and \(w_{u}^{j}\) for some \(w_{u}^{j}\) that is not matched in \(M_{X}\) but matched in \(M_{Y}\). This implies that \(u\in Y\), and we define \(v_{e}\coloneqq u\). Then, we obtain a new matching \((M_{X}\setminus E(P))\cup(E(P)\cap M_{Y})\) saturating \(V_{E}\), which induces a capacitated vertex cover \((X\cup\{u\},\alpha_{X\cup\{u\}})\) such that \(|\alpha_{X\cup\{u\}}^{-1}(v)|<|\alpha^{-1}(v)|\). We repeat this for all other edges in \(\alpha_{X\cup\{u\}}^{-1}(v)\), yielding a desired set \(W\). An analogous lemma also holds for minimal capacitated dominating sets with a sightly more involved argument. This proof is deferred to the full version of this article due to space limitations. Lemma 11: _Let \(X,Y\) be distinct minimal capacitated dominating sets of \((G,c)\) and let \(v\in X\setminus Y\). Then, there is a vertex set \(W\subseteq Y\) of size at most \(q+1\) such that \((X\setminus\{v\})\cup W\) is a capacitated dominating set of \((G,c)\)._Proof. : Let \(\beta_{X}\colon V(G)\setminus X\to X\) (resp., \(\beta_{Y}\colon V(G)\setminus Y\to Y\)) be a function such that \((X,\beta_{X})\) (resp., \((Y,\beta_{Y})\)) is a capacitated dominating set of \((G,c)\). As \(c(v)\leq q\), \(\beta_{X}^{-1}(v)\) contains at most \(q\) vertices. For each \(u\in\beta_{X}^{-1}(v)\), we define a vertex \(u^{*}\in Y\), and show that \((X\setminus\{v\})\cup W\) with \(W=\{u^{*}:u\in\beta_{X}^{-1}(v)\cup\{v\}\}\) is a capacitated dominating set of \((G,c)\). To define such a vertex \(u^{*}\) for \(u\in\beta_{X}^{-1}(v)\cup\{v\}\), we again use a similar strategy as in Proposition 2. Let \(H\) be a bipartite graph with \(V(H)=V^{\prime}\cup V\) such that \(V^{\prime}=\{w_{u}:u\in V(G)\}\) and \(V=\{w_{u}^{i}:u\in V(G),1\leq i\leq c(u)\}\).