Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:

enter image description here

We can formulate max flow as an linear programming problem with integer variables in latter.

  1. 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?

  2. Is there a formal proof of this?


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.

  • $\begingroup$ Is that one big reason why people use no linear programming to solve for perfect matching in bipartite graphs (that the optimal solution is not guaranteed to be integral even though an integral solution exists)? $\endgroup$ – Turbo May 23 at 7:30
  • $\begingroup$ There are dedicated algorithms for bipartite maximum matching, and they are likely to be faster than a reduction to LP. $\endgroup$ – Yuval Filmus May 23 at 7:32
  • $\begingroup$ Well I mean I know that complexity part. I am just wondering why would simple linear programming with real variables work (it seems the perfect matching polytope for bipartite graph is unimodular which means vertex points are integral). Still why does linear programming for $K_{2,2}$ fail? I fail to grasp. $\endgroup$ – Turbo May 23 at 7:33
  • $\begingroup$ The same counterexample also works for the LP relaxation. But every vertex does correspond to a matching, so the simplex algorithm will find a matching. $\endgroup$ – Yuval Filmus May 23 at 7:35
  • $\begingroup$ Thank you integrality with simplex programming that makes sense. However if you maximize a hyperplane on an unimodular polytope I would expect the solution to be integral since optimal solution lies on a vertex which is integral. Why does it fail for $K_{2,2}$? I still do not see it. $\endgroup$ – Turbo May 23 at 7:37

Just to respond to the above comment by the OP "why does linear programming for $K_{2,2}$ fail". Perhaps your confusion is because we need to distinguish between "solving an LP" and "solving an LP using a particular algorithm".

The LP formulation of maxflow (with real variables) has optimal solution (1,0,1,0) (for the edges of the bipartite graph $K_{2,2}$- I'm ignoring the remaining edges incident to source and sink), which corresponds to a perfect matching. The optimal solution (0,1,0,1) also corresponds to a perfect matching. Any convex combination of these two vertex points, such as (0.5,0.5,0.5,0.5) or (0.3,0.7,0.3,0.7), is also an optimal solution to the LP and therefore can be obtained if you "solve the LP".

Visualize a polygon in two dimensions whose one side corresponds to the above convex combination of two corner points. The level set of the LP cost function is parallel to this side, and we are optimizing in a direction perpendicular to this side. So "solving the LP" (i.e. without reference to any particular algorithm) can give any point (not necessarily a corner point) from this side.

The latter two solutions are not vertices, and so if you "solve the LP using an algorithm that gives a vertex solution (eg, simplex)", then you are guaranteed a matching. Am I correct?


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.