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.

  • $\begingroup$ 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.) $\endgroup$ – David Richerby Apr 18 at 16:10
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 18 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.