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

Question

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?

Answer 1

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