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.

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.