Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1), the minimum weight perfect matching problem on a complete graph $G$ with even number of vertices and weight $w:E(G)\to \mathbb{R}$, $w\ge 0$, can be reduced to the following linear program.

minimize $w^\top \cdot x$ (where $x:E(G)\to \mathbb{R}$)

subject to

(1) $x(e)\ge 0$ for each $e\in E(G)$

(2) $x(C)=1$ for each trivial odd cut $C$ (trivial cut is a cut which separates one vertex from the rest of the graph)

(3) $x(C)\ge 1$ for each non-trivial odd cut $C$.

We introduce a variable $y_C$ for each odd cut $C$.

The dual program is:

maximize $\sum_C y_C$

subject to

(D1) $y_C\ge 0$ for each non-trivial odd cut $C$

(D2) $\sum_{C~ {\rm containing~ }e} y_C\le w(e)$ for every $e\in E(G)$.

Now we assume that the weight function $w$ is a metric on the vertex set of $G$ (that is, $w(e)=$ the distance between the ends of $e$).

Question: Is it possible to show (under this assumption) that among the optimal dual solutions there is one for which $y_C\ge 0$ for all odd cuts, including trivial ones.


1 Answer 1


Since I did not get an answer to my question, I worked it out myself. The answer is "Yes". It can be obtained by following the algorithm described in Section 9.2 of Lovasz-Plummer (Matching theory). The inequality which we need is that if $S_j$ is a singleton, then $t_3\le y_{\nabla(S_j)}$. It is not difficult to derive this from the definitions and the triangle inequality for the distance corresponding to the weight $w$. (I am going to write the details in a paper.)

Added on July 3, 2019: One can find the details in Lemma 2.3 of the paper http://arxiv.org/abs/1907.01155


Your Answer

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

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