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

Question

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.

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