patternMinor
Does real linear programming produce bipartite perfect matching using maxflow reduction?
Viewed 0 times
maxflowreallinearproduceprogrammingperfectbipartitereductionusingdoes
Problem
Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:
We can formulate max flow as an linear programming problem with integer variables in latter.
-
If we do not use integer variables does solving for maxflow in linear programming formulation with only real variables still produce valid perfect matching of given graph?
-
Is there a formal proof of this?
We can formulate max flow as an linear programming problem with integer variables in latter.
-
If we do not use integer variables does solving for maxflow in linear programming formulation with only real variables still produce valid perfect matching of given graph?
-
Is there a formal proof of this?
Solution
Let us consider $K_{2,2}$, the complete bipartite graph with two vertices on either side. A valid max flow sends $1/2$ units of flow across each edge of the bipartite graph. This gives a negative answer to your first question.
On the other hand, the integral flow theorem guarantees that there exists an integral max flow, and such a max flow can be found algorithmically. An integral max flow does correspond to a maximum matching.
On the other hand, the integral flow theorem guarantees that there exists an integral max flow, and such a max flow can be found algorithmically. An integral max flow does correspond to a maximum matching.
Context
StackExchange Computer Science Q#109743, answer score: 3
Revisions (0)
No revisions yet.