It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in polynomial time.


I would like to know whether the same is true for optimal matchings with a given fixed number of edges.


The problem can be illustrated as follows: a tennis club has the task to find e.g. the 10 best pairs of players that will take part in a tournament of doubles (i.e. two players on each side). The situation can be modeled as a graph where the vertices correspond to players and the edge weights correspond to the playing strength of the pair of players.
The task is then to find 10 non-adjacent edges with maximal weight sum.



complexity of finding optimal matchings of given fixed size
With a little trick you can use the algorithm for finding an optimal matching to solve this.


Let the graph $G$ have $n$ vertices and you want to find the optimal matching with size $k$. Lets suppose that there is a matching of size $k$.


The first remark is that if you add the same constant to all edge weights then the set of optimal matchings of size $k$ will not change. So lets add a constant $C$ big enough to the weights so that every matching of $k$ size will have a bigger weight than any matching of lesser size.


Now you add $n-2k$ new vertices to the graph and connect each of these new vertices with all the old ones. The weight of these new edges should be big enough so that every optimal matching in this new graph $G'$ must use exactly $n-2k$ of these new edges (the maximum possible).


You search for an optimal matching in $G'$. It will have $n-2k$ of the new edges and so at most $k$ from the original edges of $G$. So it will find us an optimal matching in $G$ of size at most $k$. But because of our first step and because there is a matching of size $k$ in $G$ thus it will contain exactly $k$ original edges.


