2
$\begingroup$

I'm not sure this is equivalent to bipartite vertex cover question. The question is:

Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex from the left side.

e.g. In the following graph, the answer is 1, cause vertex g has connection to all vertex on the left. enter image description here

$\endgroup$
1
$\begingroup$

It is equivalent to the set cover problem. You can regard each vertex in the right side as a set of its neighbors in the left side. In your example, $e,f,g$ correspond respectively to the sets $\{d\},\{d\},\{a,b,c,d\}$. Now a minimum vertex cover in your problem is equivalent to a minimum set cover.

$\endgroup$
  • $\begingroup$ For the sake of completeness: This is a polynomial reduction from the stated vertex cover problem to Set Cover. The other direction is quite similar to achieve: For each element in the universe of the Set Cover instance, add a vertex to the left hand side. For each set in the family of sets, add a vertex on the right hand side and connect it to the corresponding vertices on the left hand side. This should be a polynomial reduction from Set Cover to this custom vertex cover problem. $\endgroup$ – Daniel Sep 25 '19 at 14:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.