# Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching.

However, I am using python-graph-tool, which only has max-cardinality max-weight matching, which from what I understand, only finds the max-weight matching of the max-cardinality matchings. However, it may be the case that a truly max-weight matching will not always be a max-cardinality matching (this is especially true on graphs that can have negative edge weights).

Are there any tricks I could use to still get what I need? For example, could I transform my graph $G \to G'$ so that by obtaining a max-card-max-weight matching on $G'$ I could obtain a max-weight matching on $G$? Or will I have to find another algorithm? Are there any good algorithms suited to the task?

Suppose that the original graph is $G = (V,E)$. Let $V’$ be a copy of $V$, and create a new graph $G’$ with vertex set $V \cup V’$ and the following edges:
• The original edges of $G$.
• For every edge $(a,b) \in E$, we add a zero-weight edge $(a’,b’)$, where $a’,b’$ are the counterparts of $a,b$ in $V’$.
• A matching connecting $V$ to $V’$ (i.e., each vertex in $V$ is connected to its counterpart in $V’$) with zero-weight edges.
Every matching of $G$ can be extended to a perfect matching of $G’$ with the same weight.
A useful feature of this reduction is that it preserves sparsity — that is, denoting by $n,m$ the number of vertices and edges in $G$, and by $n’,m’$ the same parameters for $G’$, we have $n’+m’ = O(n+m)$.
• Thanks! :) I think I understand the first solution. So... you always get a perfect matching by matching $(a,a')\ ,\ \forall a \in V$, which acts as a fall-back strategy. Whenever there is a $-$ve edge in $E$ you can match across replicas, while if there is a $+$ve edge $(u,v) \in E$ then you can match $(u,v) \in E$ and $(u',v') \in E'$. Pretty cool! However, I'm not sure I understand the second solution. If I had a 4-vertex (square) ring with side weights $+1,-1,-1,-1$, then I'm not sure how adding in zero-weight crossings will make max-card-max-weight and max-weight matchings coincide. Commented Jul 28, 2018 at 17:04