<p>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.</p>

CC BY-SA 3.0
2015-07-22T18:03:28.737Z
2015-07-22T18:03:28.737Z
David Eppstein
<p>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.</p>

<p>What is known about the problem? Do we have a polynomial time algorithm for the problem?</p>

<graph-theory><graph-algorithms><optimization>
Minimum weight matching in general graphs with additional input specifying the number of matched edges
anup
# Minimum weight matching in general graphs with additional input specifying the number of matched edges

(Asked by: username_0 on 2015-07-22)

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?

**Tags:** graph-theory, graph-algorithms, optimization


---

## 1 answers

### Answer by username_1 on 2015-07-22. Score: 9 | Accepted answer

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.


---

