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) withm=|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?
Minimum weight matching in general graphs with additional input specifying the number of matched edges
graph theory;graph algorithms;optimization
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.