# Maximum matching using linear programming

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).