## 4 Minimal Connected Vertex Cover Enumeration
### General Graphs
Thus, we consider the other case. Observe that \(|\mathcal{S}(H-v,L)|\leq|\mathcal{S}(H,L)|\) for any \(v\in R\). Moreover, we claim that \(|\mathcal{S}(H_{v},L_{v})|\leq|\mathcal{S}(H,L)|\) for any \(v\in R\). Let \(W\in\mathcal{S}(H_{v},L_{v})\). From Lemma 4, \(W\cup\{v\}\) is a valid augmentation for \(L\) in \(H\). Moreover, all vertices in \(W\) are cut vertices in \(H[L\cup W]\) as they are cut vertices in \(H_{v}[L_{v}\cup W]\). Thus, either \(W\) or \(W\cup\{v\}\) is a minimal valid augmentation for \(L\) in \(H\). This indicates that there is an injection \(\phi\) from \(\mathcal{S}(H_{v},L_{v})\) to \(\mathcal{S}(H,L)\) by setting \(\phi(W)=W\) or \(\phi(W)=W\cup\{v\}\) for all \(W\in\mathcal{S}(H_{v},L_{v})\), proving the claim \(|\mathcal{S}(H_{v},L_{v})|\leq|\mathcal{S}(H,L)|\). This also proves that \(|\mathcal{S}(H_{X},L_{X})|\leq|\mathcal{S}(H,L)|\) for \(X\subseteq R\). Now, we turn to showing that \(T(\ell,r,N)\leq(\ell\cdot r+N)^{c\log(\ell\cdot r)}\) for some constant \(c\). For simplicity, we assume that both \(\ell\) and \(r\) are even. Observe that given a collection of valid augmentations \(\mathcal{A}\), one can compute \(\min_{H,L}(\mathcal{A})\) in time \(O(n^{2}|\mathcal{A}|)\) using a standard data structure. Suppose that there is a vertex \(v\in R\) with \(|N_{H}(v)|>|L|/2\). In this case, \(L_{v}\) has at most \(|L|/2\) vertices. Moreover, both \(H_{v}\) and \(H-v\) have at most \(r-1\) vertices on the \"right-hand side\". Since \(|\mathcal{S}(H,L)|\geq|\mathcal{S}(H_{v},L_{v})|\), we have \[T(\ell,r,N)\leq\underbrace{T(\ell/2,r-1,N)}_{\text{rec. call at line 9}}+ \underbrace{T(\ell,r-1,N)}_{\text{rec. call at line 11}}+dn^{2}N\]  
for some constant \(d\). Suppose otherwise that \(|N_{H}(v)|\leq|L|/2\). For \(W\in\mathcal{S}(H_{\
u},L_{\
u})\), we have \(L\setminus N_{H}(v)\)\(\subseteq N_{H}(W)\). As \(H_{\
u}[L_{\
u}\cup W]\) is connected, each connected component of \(H[L\cup W]\) contains at least one vertex in \(N_{H}(v)\). This implies that \(L_{W}\) contains at most \(|N_{H}(v)|\leq|L|/2\) vertices. Hence, we have  
\[T(\ell,r,N) \leq\underbrace{T(\ell,r-1,N)}_{\text{rec. call at line 9}}+ \underbrace{\left|\mathcal{S}(H_{\
u},L_{\
u})\right|\cdot T(\ell/2,r-1,N)}_{ \text{rec. calls at line 14}}+dn^{2}N\cdot\left|\mathcal{S}(H_{\
u},L_{\
u})\right|\] \[\leq T(\ell,r-1,N)+N\cdot T(\ell/2,r-1,N)+dn^{2}N^{2}\]  
for some constant \(d\). By combining the above two cases, we have  
\[T(\ell,r,N) \leq T(\ell,r-1,N)+\max\{T(\ell/2,r-1,N),N\cdot T(\ell/2,r-1,N)\}\] \[=T(\ell,r-1,N)+N\cdot T(\ell/2,r-1,N)+dn^{2}N^{2}\] \[\mathcal{N}^{+}(X)=\{\mu((X\setminus\{v\})\cup N(v)\cup W):v\in X,\]0 \[\mathcal{N}^{+}(X)=\{\mu((X\setminus\{v\})\cup N(v)\cup W):v\in X,\]1 \[\mathcal{N}^{+}(X)=\{\mu((X\setminus\{v\})\cup N(v)\cup W):v\in X,\]2 \[\mathcal{N}^{+}(X)=\{\mu((X\setminus\{v\})\cup N(v)\cup W):v\in X,\]3  
By taking a sufficiently large constant \(c\), we have \(T(\ell,r,N)\leq(\ell\cdot r+N)^{c\log(\ell\cdot r)}\). Overall, we have the following theorem. Theorem 4.2: _There is an algorithm for enumerating minimal connected vertex covers of an \(n\)-vertex graph \(G\) in total time \((n+|\mathcal{S}_{\text{cvc}}|)^{O(\log n)}\)._