1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Paradox Jul 28 '18 at 17:04
  • $\begingroup$ Yes, I’m not sure it works. It doesn’t matter, since the first solution is better anyhow. $\endgroup$ – Yuval Filmus Jul 28 '18 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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