0
$\begingroup$

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).

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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