Take the 2-minute tour ×
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.

Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds).

Intuitively: for each flow, pick one endpoint, then it is a minimum vertex cover in bipartite graph. But can it be shown rigorously?

share|improve this question

migrated from cstheory.stackexchange.com Jun 3 '12 at 3:44

This question came from our site for theoretical computer scientists and researchers in related fields.

2 Answers 2

According to König's theorem, the size of minimum vertex cover in bipartite graph $G$ equals to the size of maximum matching in $G$, and there is an obvious reduction from maximum matching in bipartite graph to maxflow problem.

share|improve this answer
1  
If you want to make this answer better, you should outline the idea of the reduction. –  Raphael Jun 3 '12 at 14:28

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, either node $u$ or $v$ will be a part of the minimum vertex cover.

Draw this and you will understand.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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