I am looking for an algorithm that can compute a maximum weight matching among all matchings with at least $k$ edges for some integer $k$. Note that this matching may have smaller weight than an unconstrained max weight matching.
As an example, consider the graph consisting of two triangles joined by a single edge (called the link). One of the edges in each triangle that is adjacent to the link has a weight of 2. The remaining edges have weight 1. The max weight matching consists of the two heavy edges and has weight 4. The max weight matching with at least 3 edges includes the link and one of the light edges in each triangle, for a weight of 3.
For bipartite graphs this problem is easy, using the well-known reduction to min cost flow (add source and sink vertices with edges from the source to the "input vertices" and edges from the "output vertices" to the sink, negate the weights to get the edge costs, all edge capacities are 1) and using a min-cost augmenting path algorithm. When finding an unconstrained max weight matching, one halts the algorithm when the augmenting paths no longer have negative weight. However, if one allows the algorithm to continue running until $k$ of the original edges have positive flow, the resulting matching is the one we want.
I have been looking for a similar way to extend Edmond's blossom-shrinking algorithm for weighted graphs. While one can continue to run the algorithm so long as there are edges with tight dual constraints that can be processed, the algorithm gets blocked if a relabeling step is required. The trouble is that once the dual variables at the unmatched vertices become zero, there is no way to continue.
I have thought about extending the LP on which Edmond's algorithm is based, by adding a constraint of the form $\sum x_e \geq k$ where the sum is over all edges $e$ and $x_e$ is the selection variable for $e$. However, it's not clear to me how to establish an initial feasible solution for both the primal and dual problems that will work with Edmond's algorithm.
