patternMinor
Reducing minimum vertex cover in a bipartite graph to maximum flow
Viewed 0 times
maximumgraphflowvertexminimumreducingbipartitecover
Problem
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. But can it be shown rigorously?
Solution
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.
Context
StackExchange Computer Science Q#2208, answer score: 3
Revisions (0)
No revisions yet.