7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – xuhdev Apr 25 '16 at 0:11
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you want to make this answer better, you should outline the idea of the reduction. $\endgroup$ – Raphael Jun 3 '12 at 14:28
2
$\begingroup$

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.

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

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.