4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Feb 25, 2022 at 15:51
  • $\begingroup$ Yes, I am looking for a simple and natural reduction. $\endgroup$
    – AngryLion
    Feb 25, 2022 at 16:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.