# Matching with specific cardinality

In a weighted graph $$G(\mathcal{V},\mathcal{E})$$ where $$w(i,j)$$ is the weight of the edge $$(i,j) \in \mathcal{E}$$. How can I find a maximum weighted matching with a specific size (i.e specific cardinality).

Let me start by answering a slightly different question: Given a weighted graph $$G=(V,E)$$ on $$n=|V|$$ vertices, we want to find a maximum-weight matching of cardinality at most $$k$$.

Let $$L$$ be the largest edge weight in $$G$$, and define $$L' = 2nL$$. Transform the graph $$G$$ by adding $$\ell =n-2k$$ new vertices $$v_1, \dots, v_\ell$$, and all edges in $$\{v_1, \dots, v_\ell\} \times V$$. Each new edge has weight $$2nL$$. Let $$G'$$ be the new graph. Compute a maximum matching $$M$$ of $$G'$$ and return the matching $$M \cap E$$.

If there is a matching $$M$$ of weight $$\ell L' + x$$ in $$G'$$ then there is a matching of weight $$x$$ and size at most $$k$$ in $$G$$.

There are exactly $$\ell$$ edges in $$M' = M \cap (\{v_1, \dots, v_\ell\} \times V)$$ since at most $$\ell$$ edges in $$\{v_1, \dots, v_\ell\} \times V$$ can belong to any single matching and, if $$|M| < \ell$$, the weight of $$M$$ would be at most $$(\ell-1)L' + \frac{n+\ell}{2}L < (\ell-1)L' + nL < \ell L'$$. Then, there are at most $$k$$ edges in $$M'' = M \setminus M' = M \cap E$$ as otherwise we would have $$|M| = |M'| + |M''| > \ell + k = \frac{\ell}{2} + \frac{\ell}{2} + k = \frac{\ell}{2} + \frac{n}{2} - k + k = \frac{\ell + n}{2}$$, which is a contradiction. Since the weight of $$M'$$ is exactly $$\ell L'$$, the weight of $$M'' \subseteq E$$ must be $$x$$.

If there is a matching $$M''$$ of weight $$x$$ and size at most $$k$$ in $$G$$ then there is a matching $$M$$ of weight $$\ell L' + x$$ in $$G'$$.

Since $$|M''| \le k$$, there are at least $$n-2k= \ell$$ distinct unmatched vertices $$u_1, \dots, u_\ell$$ in $$V$$ (w.r.t. $$M''$$). Choose $$M = M'' \cup \{ (v_i, u_i) \mid i=1, \dots, \ell\}$$. The weight of $$M$$ is $$\ell L' + x$$.

We can now look for a maximum-weight matching of cardinality exactly $$k$$ in $$G$$. We can reduce this problem to the one of finding a maximum-weight matching of cardinality at most $$k$$.

Given $$G=(V,E)$$ let $$L$$ be its largest edge weight. Modify $$G$$ by changing the weight $$w(u,v)$$ of each edge $$(u,v)$$ to $$w'(u,v) = w(u,v) + kL$$. Call $$G'$$ the resulting graph. Find a maximum-weight matching $$M$$ of cardinality at most $$k$$ in $$G'$$. If $$|M| < k$$, the instance has no feasible solution, otherwise return $$M$$.

Clearly a matching $$M$$ of size $$k$$ in $$G'$$ weighs $$kL + x$$ if and only if $$M$$ weighs $$x$$ in $$G$$. We only need to show that: 1) if a matching of size $$k$$ exists in $$G$$, $$M$$ contains exactly $$k$$ edges, and 2) if no feasible matching exists in $$G$$, $$M$$ contains less than $$k$$ edges.

The second claim is immediate since any matching in $$G'$$ is also a matching in $$G$$. We then focus on the first claim:

If $$G$$ admits a matching of size $$k$$, $$M$$ contains exactly $$k$$ edges

By construction $$|M| \le k$$. We now show that $$|M| \ge k$$. Suppose towards a contradiction that $$M < k$$. Then the weight of $$M$$ is at most $$\sum_{(u,v) \in M} w'(u,v) \le (k+1) |M| L \le (k+1)(k-1)L = (k^2 - 1)L < k^2 L$$. Since a weight of at least $$k^2 L$$ is attainable by selecting the edges in any matching of size $$k$$ in $$G'$$ (such a matching exists in $$G$$ and hence in $$G'$$), this contradicts the fact that $$M$$ is a maximum-weight matching.

.