# Reducing counting minimal vertex covers to counting minimum cardinality vertex covers

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 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.

• 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? Feb 25 at 15:51
• Yes, I am looking for a simple and natural reduction. Feb 25 at 16:14