4
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.