## 4 Minimal Connected Vertex Cover Enumeration
### General Graphs
The algorithm recursively generates minimal valid augmentations for \(L\) in \(H\) unless \(\min(|L|,|R|)\leq 1\). Let \(v\) be an arbitrary vertex in \(R\). We enumerate all sets in \(\mathcal{S}(H,L)\) by separately generating those including \(v\) and those excluding \(v\). The following lemma ensures that this strategy correctly enumerates all minimal valid augmentations. Lemma 5: \(\mathcal{S}(H,L)=\mathcal{S}(H-v,L)\cup\mathtt{min}_{H,L}(\mathcal{S}(H_{v},L_ {v})+v)\)_._  
Proof: From Lemma 4, \(\mathcal{S}(H_{v},L_{v})+v\) is a valid augmentation for \(L\) in \(H\). Since each valid augmentation in \(\mathcal{S}(H-v,L)\) is also a minimal valid augmentation for \(L\) in \(H\), we have  
\[\mathcal{S}(H-v,L)\cup\mathtt{min}_{H,L}(\mathcal{S}(H_{v},L_{v})+v)\subseteq \mathcal{S}(H,L).\]  
Let \(W\in\mathcal{S}(H,L)\) be a minimal valid augmentation for \(L\) in \(H\). If \(v\) is not contained in \(W\), \(W\) is a minimal valid augmentation for \(L\) in \(H-v\) as well, implying that \(W\in\mathcal{S}(H-v,L)\). Suppose otherwise. Using Lemma 3, it holds that \(W\setminus\{v\}\in\mathcal{S}(H_{v},L_{v})\). Hence, we have \(W\in\mathtt{min}_{H,L}(\mathcal{S}(H_{v},L_{v})+v)\). From Lemma 5, we can enumerate all minimal valid augmentations in \(\mathcal{S}(H,L)\) by enumerating those in \(\mathcal{S}(H-v,L)\) and in \(\mathcal{S}(H_{v},L_{v})\) separately and just combining them. The following lemma gives another way to enumerate them. Lemma 6: \(\mathcal{S}(H,L)=\mathtt{min}_{H,L}\left(\bigcup_{W\in\mathcal{S}(H_{v},L_{v} )}\mathcal{S}(H_{W}-v,L_{W})+W\right)\cup\mathtt{min}_{H,L}(\mathcal{S}(H_{v},L_{v})+v)\)_._  
Proof: From Lemma 5, it suffices to show  
The above lemmas enable us to enumerate minimal valid augmentations in \(\mathcal{S}(H,L)\) with two methods. Suppose that \(L\) contains at least two vertices. In our algorithm, we select a vertex \(v\in R:=V(H)\setminus L\) of highest degree among \(R\). If \(v\) has at most one neighbor, we conclude that there is no valid augmentation for \(L\) in \(H\) at all, as \(|L|\geq 2\). If \(v\) has more than \(|L|/2\) neighbors in \(L\), we adopt the first method; we adopt the second method otherwise. Algorithm 1 recursively employs this branching strategy until \(\min(|L|,|V(H)\setminus L|)\leq 1\). ```
1 ProcedureMinValidAug(\(H,L\))
2 Let \(R=V(H)\setminus L\). 3 if\(\min(|L|,|R|)\leq 1\)then
4 return all minimal valid augmentations computed by a brute-force algorithm. 5 Let \(v\) be a highest degree vertex in \(R\). 6 if\(|N(v)|\leq 1\)then
7 return\(\emptyset\)
8\(\leftarrow\emptyset\)
9\(\mathcal{S}_{v}\leftarrow\)MinValidAug(\(H_{v},L_{v}\))
10 if\(|N(v)|>|L|/2\)then
11 returnMinValidAug(\(H-v,L\)) \(\cup\)min\({}_{H,L}(\mathcal{S}_{v}+v)\)
12 else
13 foreach\(W\in\mathcal{S}_{v}\)do
14\(\mathcal{S}\leftarrow\mathcal{S}\cup\min_{H,L}(\text{MinValidAug}(H_{W}-v,L_{ W})+W)\)
15 return\(\mathcal{S}\cup\min_{H,L}(\mathcal{S}_{v}+v)\)
```  
**Algorithm 1**An output quasi-polynomial time algorithm for enumerating minimal valid augmentations. The correctness of Algorithm 1 directly follows from Lemmas 5 and 6. We then analyze the running time of Algorithm 1. Let \(T(\ell,r,N)\) be the worst case running time of Algorithm 1 when a bipartite graph \(H\) with a color class \(L\) that satisfies \(|L|\leq\ell\), \(|V(H)\setminus L|\leq r\), and \(|\mathcal{S}(H,L)|\leq N\) is given as input. Clearly, \(T(\ell,r,N)\leq T(\ell^{\prime},r^{\prime},N^{\prime})\) for \(\ell\leq\ell^{\prime}\), \(r\leq r^{\prime}\), and \(N\leq N^{\prime}\). Lemma 7: _For \(\ell,r,N\in\mathbb{N}\) with \(n=\ell+r\), it holds that \(T(\ell,r,N)=(n+N)^{O(\log n)}\)._  
Proof: We prove the following claim by induction on \(n\): \(T(\ell,r,N)\leq(\ell\cdot r+N)^{c\log(\ell\cdot r)}\) for some constant \(c\). Let \(H=(L\cup R,E)\) be a bipartite graph with \(|L|\leq\ell\), \(|R|\leq r\), and \(|\mathcal{S}(H,L)|\leq N\). If \(\min(|L|,|V(H)\setminus L|)\leq 1\), then \(T(\ell,r,N)\) is upper bounded by a polynomial in \(n\), as each set in \(\mathcal{S}(H,L)\) has at most two vertices.