Maximum weight matching instead of maximum weight maximal cardinality

[mburq]

Hello, It seems that the lp formulation for maximum_weight_maximal_matching enforces that all the nodes in v1 (i.e. the smaller partition of the vertices) have to be matched (l 65 of lp.jl) This is not always feasible, and in general it might be complicated to find the maximum weight matching among matchings of maximum cardinality.

However it would be quite simple to fix the code if we restrict to finding maximum weight matchings (with no restriction on the cardinality).

Thoughts ?

[CarloLucibello]

maximum weight matching is a slightly different problem, so it should be implemented in another (similar) function. I'm not entirely sure that linear programming yields an integer solution in that case, even for bipartite graphs. Probably it does, but I'm not sure

[mburq]

Agreed it's not exactly the same problem, we can add a function so we have both options. Indeed for a bipartite graph it reduces to a network flow problem therefore integrality of the LP solution is guaranteed.

We can also have a IP formulation that allows for general graphs (it stays fast for bipartite graphs, but for non-bipartite large graphs it may get quite slow).

[sbromberger]

@mburq - were you planning on submitting a PR for this work? Should I close the issue?

[CarloLucibello]

this has been closed in #23

[sbromberger]

Cool - thanks for the confirmation.