Let $G=(V,E)$ be a general graph, where edges have weights $w(e)$ and $|V|$ is even.
One of the classic problem is to find a maximum-weight perfect matching (MWPM) of the graph G.
The MWPM problem can be solved by the famous Edmond's algorithm.
We assume the graph G has at least one perfect matching.
I am interested in a more general problem, in which the cardinality of the matched vertices are constrained by a certain (even) value $M$ (That is, the number of matched vertices in the solution is exactly $M$). For example, if $M=|V|$, the problem becomes the classic MWPM problem.
Any hints or clues are appreciated.
Best Answer
Add $|V|-M$ vertices adjacent to every vertex of $G$, with zero cost on each of their edges. Then solve the perfect matching problem.