In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to solve the following LP:
$$ \text{maximize}~~\sum_{e\in E} w_e x_e \\ \text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V \\ 0\le x_{e}\le 1\text{ for }e\in E. $$
If some value $x_e$ in the optimal solution is fractional, then there must be another fractional $x_{e'}$ near the same vertex (since the sum of all edges near each vertex is 1). By following these fractional edges, we eventually find a cycle of fractional edges. We can then move value along the edges in the cycle until at least one edge becomes integral (0 or 1).
A crucial aspect in this solution is that all such cycles are of even length, since the graph is bipartite. If the graph is not bipartite, then the above scheme does not work since we might have odd-length cycles.
QUESTION: Is there a similar algorithm for finding a maximum-cardinality matching, even in unweighted graphs, based on rounding a fractional solution to the above LP?
(I know that this problem can be solved by the blossom algorithm, but it is very complicated and I am hoping that the LP approach can yield a simpler algorithm).
2 Answers 2
This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and combinatorial optimization. Edmonds gave a description of the general matching polytope, which has exponentially many defining linear inequalities. While the simplex method cannot be used to optimize the corresponding linear program, other approaches, such as the ellipsoid algorithm and some interior point methods, can use a separation oracle for efficient optimization (at least theoretically).
There is a third algorithm, due to Micali and V. Vazirani, which is however also quite complicated; see the recent exposition by Vazirani.
You can start by modeling the LP problem as in the bipartite case. Then you optimize.
- If the solution found has fractional values, then, there is an odd cycle with fractional values in the subgraph induced by the solution, and you have to add the corresponding "blossom inequality constraint" to your LP model "to break" the odd cycle.
- Then you optimize again the augmented LP model.
By repeating this steps, eventually, you will arrive to an integer solution corresponding to a matching.
Here there is a video showing an example: https://youtu.be/lLb52UobMh0