# Reducing minimum vertex cover in a bipartite graph to maximum flow

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?

• "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 '16 at 0:11

## 2 Answers

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.

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

• How will you choose sets A and B? – Abhishek Bhatia Dec 4 '17 at 3:25
• @AbhishekBhatia they are defined by the bipartite graph. – karlosss Nov 14 '19 at 22:02