Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of edges that the matching can use. In other words, given a graph G=(V,E) with m=|E| and an integer k, where m and k are different in general, we need to find a matching of minimum weight that uses exactly k edges.
What is known about the problem? Do we have a polynomial time algorithm for the problem?
Add $n-2k$ extra vertices, each connected to all the original vertices with zero-weight edges, and add a large enough number $W$ to each of the original edges to make their weights all positive. Then look for the minimum weight perfect matching.
