HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Reducing minimum vertex cover in a bipartite graph to maximum flow

Submitted by: @import:stackexchange-cs··
0
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?

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.