# On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights

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.

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