## 4 Minimal Connected Vertex Cover Enumeration
### General Graphs
Therefore, if there is an output-polynomial time algorithm for Minimal Connected Vertex Cover Enumeration, we can enumerate all minimal transversals of \(\mathcal{H}\) in output-polynomial time as well. Now, we modify a bipartite graph \(G\) into a 2-degenerate bipartite graph \(G^{\prime}\). Let \(w_{e}\) be a vertex in \(V_{\mathcal{E}}\) and \(\{u_{1},\ldots,u_{d}\}\subseteq V\) be the set of vertices that are contained in \(e\). We replace \(w_{e}\in V_{\mathcal{E}}\) and the pendant vertex \(w^{\prime}_{e}\) with a path \(P_{e}=(p^{e}_{1},\ldots,p^{e}_{2d+1})\) and \(2d+1\) pendant vertices, each of which is adjacent to \(p^{e}_{i}\) for each \(p^{e}_{i}\). Furthermore, we add an edge \(\{u_{j},p^{e}_{2j-1}\}\) for each \(1\leq j\leq d\). Figure 1 illustrates this replacement. We do this for each \(e\in\mathcal{E}\), and it is easy to observe that the graph \(G^{\prime}\) obtained in this way is bipartite. Moreover, we claim that \(G\) is 2-degenerate: we first eliminate all the pendant vertices of \(G^{\prime}\), the vertices of \(P_{e}\) that have even indices, the remaining vertices of \(P_{e}\), the vertices in \(V\), and then \(r\). This elimination ordering is indeed a 2-degeneracy ordering, that is, each eliminated vertex has at most two neighbors in the graph induced by the non-eliminated vertices. The pendant vertices attached to \(P_{e}\) ensure that all the vertices of \(P_{e}\) are included in every minimal connected vertex cover of \(G^{\prime}\) from Lemma 2, and hence there is a one-to-one correspondence between the set of minimal connected vertex covers of \(G^{\prime}\) and the set of minimal transversals of \(\mathcal{H}\) as well. We next discuss an extension of the previous algorithm to general graphs. Although the algorithm described in the previous subsection also works for general graphs, its delay can be exponential in \(n\). In order to cope with this exponential running time bound, we refine the definition of \(\mathcal{N}^{+}\) and prove that \(\mathcal{N}^{+}(X)\) can be generated with a better running time bound for \(X\in\mathcal{S}_{\text{cyc}}\). Figure 1: The left (**a**) and center (**b**) figures illustrate a hypergraph \(\mathcal{H}\) and the constructed graph \(G\), respectively. In (**b**), filled circles indicate a minimal connected vertex cover of \(G\). The right figure (**c**) illustrates a part of the construction of a 2-degenerate graph \(G^{\prime}\) from \(G\). We first observe that the algorithm also works even when \(\mathcal{N}^{+}\) is modified into  
\[\mathcal{N}^{+}(X)=\{\mu((X\setminus\{v\})\cup N(v)\cup W):v\in X,\] \[\text{$W$ is a minimal valid augmentation for $(X\setminus\{v\})\cup N(v)$}\},\]  
where a _minimal valid augmentation_ for a vertex cover \(X^{\prime}\) is an inclusion-wise minimal \(W\) such that \(G[X^{\prime}\cup W]\) is connected. In other words, the directed graph \(\mathcal{D}\) defined on this modified neighborhood is strongly connected as well. In the following, we show that for \(X\in\mathcal{S}_{\text{cvc}}\), \(\mathcal{N}^{+}(X)\) can be generated in time \((n+|\mathcal{N}^{+}(X)|)^{O(\log n)}\), which yields an _output quasi-polynomial time bound_\((n+|\mathcal{S}_{\text{cvc}}|)^{O(\log n)}\) for Minimal Connected Vertex Cover Enumeration due to Theorem 1. In order to enumerate all the sets in \(\mathcal{N}^{+}(X)\), it suffices to enumerate all minimal valid augmentations for \((X\setminus\{v\})\cup N(v)\) for each \(v\in X\). Let \(v\in X\) and let \(X^{\prime}=(X\setminus\{v\})\cup N(v)\). Recall that \(X^{\prime}\) is a vertex cover of \(G\). To simplify the following discussion, we construct a bipartite graph \(H\) with color classes \(L\) and \(R\) as follows. For each connected component \(C\) in \(G[X^{\prime}]\), \(L\) contains a vertex \(v_{C}\), and we define \(R\coloneqq V(G)\setminus X^{\prime}\). Note that \(V(G)\setminus X^{\prime}\) is an independent set of \(G\). For \(v_{C}\in L\) and \(w\in R\), they are adjacent in \(H\) if and only if \(w\) has a neighbor in \(C\).