<p>Consider two problems.</p>
<p><strong>Problem 1</strong>: Given a graph <span class="math-container">$G = (V, E)$</span>, find the number of minimum cardinality vertex covers of <span class="math-container">$G$</span>.</p>
<p><strong>Problem 2</strong>: Given a graph <span class="math-container">$G = (V, E)$</span>, find the number of minimal vertex covers of <span class="math-container">$G$</span>.</p>
<p>A vertex cover <span class="math-container">$S$</span> is said to be a &quot;minimum cardinality vertex cover&quot; if and only if there is no vertex cover with fewer vertices.</p>
<p>A vertex cover <span class="math-container">$S$</span> is said to be a &quot;minimal vertex cover&quot; if and only if there is no proper subset of <span class="math-container">$S$</span> that is a vertex cover.</p>
<p>It can be <a href="https://epubs.siam.org/doi/pdf/10.1137/S0097539797321602" rel="nofollow noreferrer">checked</a> that both of these problems are <span class="math-container">$\#\text{P}$</span> complete. So, there should be a reduction from Problem 2 to 1 and vice versa.
What is a simple and natural reduction from Problem 2 to Problem 1?</p>
<p>The other direction can be observed from the linked paper.</p>

CC BY-SA 4.0
2022-02-25T15:51:44.943Z
We know the reduction exists, because as you point out the problems are #P-complete.  And (with some care) such a reduction could be explicitly described.  Presumably that's not what you are looking for?  Are you looking for a particularly simple or natural reduction?
Neal Young
CC BY-SA 4.0
2022-02-25T16:14:24.027Z
Yes, I am looking for a simple and natural reduction.
AngryLion
<cc.complexity-theory><graph-theory><counting-complexity><reductions><vertex-cover>
Reducing counting minimal vertex covers to counting minimum cardinality vertex covers
AngryLion
# Reducing counting minimal vertex covers to counting minimum cardinality vertex covers

(Asked by: username_0 on 2022-02-25)

Consider two problems.

**Problem 1**: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$.

**Problem 2**: Given a graph $G = (V, E)$, find the number of minimal vertex covers of $G$.

A vertex cover $S$ is said to be a "minimum cardinality vertex cover" if and only if there is no vertex cover with fewer vertices.

A vertex cover $S$ is said to be a "minimal vertex cover" if and only if there is no proper subset of $S$ that is a vertex cover.

It can be [checked](https://epubs.siam.org/doi/pdf/10.1137/S0097539797321602) that both of these problems are $\#\text{P}$ complete. So, there should be a reduction from Problem 2 to 1 and vice versa.
What is a simple and natural reduction from Problem 2 to Problem 1?

The other direction can be observed from the linked paper.

**Tags:** cc.complexity-theory, graph-theory, counting-complexity, reductions, vertex-cover
> **Comments:**
> **username_1**: We know the reduction exists, because as you point out the problems are #P-complete.  And (with some care) such a reduction could be explicitly described.  Presumably that's not what you are looking for?  Are you looking for a particularly simple or natural reduction?  
> **username_0**: Yes, I am looking for a simple and natural reduction.  

---

## 0 answers

