# Find a minimum weight matching of a specific size

Given a positive-weighted complete graph $$G=(V,E)$$ and an even integer $$k$$, I want to find a minimum weight matching of size exactly $$k$$, i.e., I want to choose $$k/2$$ vertex disjoint edges such that the summation of their weight is minimum.

• Note that minimum versus maximum makes no difference: if your biggest edge weight is $M$, then replacing every edge weight $w$ with $M-w+1$ gives a graph in which the maximum-weight size-$k$ matching is the minimum-weight one in the original graph. (The "$+1$" is so that all the weights remain positive.) – David Richerby Apr 18 at 16:10
• I was going to say to take the $k$ lightest edges of a minimum-weight perfect matching but it feels like that doesn't actually work. The idea was that any partial matching of a complete graph can be extended to a perfect matching (that's not true for arbitrary graphs), but I don't see any reason why a minimum-weight size-$k$ matching would necessarily extend to a minimum-weight perfect matching -- perhaps the $k$ edges you already chose in the partial matching force you to pick heavy edges in the extension to a perfect matching. – David Richerby Apr 18 at 17:23