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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.

    
"Intuitively: for each flow, pick one endpoint, then it is a minimum vertex cover in bipartite graph." This is not true. Consider the case of 3 vertices and 2 edges. – xuhdev Apr 25 at 0:11

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|cite|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|cite|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.