## 4 Minimal Connected Vertex Cover Enumeration
### General Graphs  
We complement the polynomial-delay enumeration algorithm in the previous subsection by showing that Minimal Connected Vertex Cover Enumeration is \"not so easy\", even on bipartite graphs. For a hypergraph \(\mathcal{H}=(V,\mathcal{E})\), a _transversal_ of \(\mathcal{H}\) is a vertex subset \(S\subseteq V\) such that each hyperedge contains at least one vertex of \(S\). Recall that no output-polynomial time algorithm for enumerating minimal transversals in hypergraphs is known so far, and several similar \"hardness\" results are discussed in the literature [37; 38]. Before providing the proof of hardness, we present a lemma that is useful for our hardness proof. Lemma 2: _Let \(G\) be a graph and \(p\) be a vertex of degree \(1\). Suppose that the unique neighbor \(q\) of \(p\) has degree at least \(2\). Then, \(p\
otin C\) and \(q\in C\) for any minimal connected vertex cover \(C\) of \(G\)._  
Proof: Since \(C\) is a vertex cover of \(G\), \(C\) contains at least one of \(p\) and \(q\). Since \(G[C]\) is connected and \(q\) has a neighbor other than \(p\), it holds that \(q\in C\). Suppose that \(\{p,q\}\subseteq C\). Then, \(C\setminus\{p\}\) is a connected vertex cover of \(G\), contradicting minimality. Thus, we have \(p\
otin C\) and \(q\in C\). Theorem 4.3: _If there is an output-polynomial time (or a polynomial-delay) algorithm for Minimal Connected 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: We first give a construction of a bipartite graph \(G\) from a hypergraph \(\mathcal{H}\) and show that there is a bijection between the collection of minimal connected vertex covers of \(G\) and that of minimal transversals of \(\mathcal{H}\). We then transform the bipartite graph \(G\) into a \(2\)-degenerate bipartite graph while keeping this bijection. Let \(\mathcal{H}=(V,\mathcal{E})\) be a hypergraph. We construct a bipartite graph \(G\) as follows. We start with the incidence bipartite graph of \(\mathcal{H}\), that is, the vertex set of \(G\) consists of two independent sets \(V\) and \(V_{\mathcal{E}}=\{w_{e}:e\in\mathcal{E}\}\), and two vertices \(v\in V\) and \(w_{e}\in V_{\mathcal{E}}\) are adjacent if and only if \(v\in e\). From this bipartite graph, we add a pendant vertex \(w^{\prime}_{e}\) that is only adjacent to \(w_{e}\) for each \(w_{e}\in V_{\mathcal{E}}\) and a vertex \(r\) that is adjacent to all vertices in \(V\). To complete the construction of \(G\), we add a pendant vertex \(r^{\prime}\) that is adjacent to \(r\). See Figure 1 for an illustration. In the following, we show that there is a bijection between the collection of minimal connected vertex covers of \(G\) and that of minimal transversals of \(\mathcal{H}\). Let \(C\) be an arbitrary minimal connected vertex cover of \(G\). From Lemma 2, \(w_{e}\in C\) and \(w^{\prime}_{e}\
otin C\) for all \(e\in\mathcal{E}\). Let \(S=C\cap V\). It is easy to see that \(C\setminus S=V_{\mathcal{E}}\cup\{r\}\) is a vertex cover of \(G\). Due to the connectivity of \(C\), for every \(e\in\mathcal{E}\), \(C\) contains at least one vertex of \(V\) that is adjacent to \(w_{e}\). This implies that \(S\) is a transversal of \(\mathcal{H}\). If there is \(v\in S\) such that \(S\setminus\{v\}\) is a transversal of \(\mathcal{H}\), \(C\setminus\{v\}\) is a connected vertex cover of \(G\) as every \(w_{e}\in V_{\mathcal{E}}\) has a neighbor in \(S\setminus\{v\}\), contradicting the minimality of \(C\). Thus, \(S\) is a minimal transversal of \(\mathcal{H}\). It is straightforward to verify that this relation is reversible, that is, for every minimal transversal \(S\) of \(\mathcal{H}\), \(S\cup V_{\mathcal{E}}\cup\{r\}\) is a minimal connected vertex cover of \(G\). From a hypergraph \(\mathcal{H}\), we can construct the graph \(G\) in polynomial time.