Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote -2 down vote favorite

Show that the problem of finding the minimum vertex cover in a bipartite graph reduces to finding a maximum flow. Describe the reduction in a precise and concise way.

share|improve this question
Why linear programming as a tag? – The Unfun Cat Nov 9 '12 at 10:28
@david: You are posting here for the first time. So let me point out some general rules to get a useful answer. Say what you have tried, where have you been stuck? Also it might be helpful not to phrase your question as a textbook question. – A.Schulz Nov 9 '12 at 10:40
-1 for duplicate: cs.stackexchange.com/questions/2208/… Of course, I find the answer there not really an answer at all, just a link. – The Unfun Cat Nov 9 '12 at 10:52
Did you try Google? – JeffE Nov 9 '12 at 16:15

closed as not a real question by A.Schulz, JeffE, Gilles♦ Nov 9 '12 at 22:05

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

1 Answer

up vote 1 down vote

Call the two partitions of the nodes $A$ and $B$. Add two new nodes, a source $s$ and a sink $t$. Connect the start node to all nodes in $A$ with an edge with max capacity of one. Connect all the nodes in $B$ to the sink with edges with a max capacity of one. And lastly give all the original edges in the graph a max capacity of one. Now finding the max flow from $s$ to $t$ will find the minimum vertex cover.

For each edge $(u,v)$ included in the max-flow, the nodes $u$ and $v$ will be a part of the minimum vertex cover.

Draw this and you will understand.

share|improve this answer

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