2
$\begingroup$

enter image description here

In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn enter image description herebelow.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The claim is true of the G is a metric space. That is, if you take the shortest path distances induced by the edge lengths and complete the graph then T-join on V is same as min-cost perfect matching. $\endgroup$
    – Chandra Chekuri
    Nov 1, 2020 at 15:10

1 Answer 1

Reset to default
2
$\begingroup$

The statement of the problem is incorrect.

But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is:

Assume $G$ is connected.

Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the length of the shortest path between vertices $a$ and $b$ in $G$. Now, find a minimum weight perfect matching in $G'$. This gives the minimum $T$-join in $G$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, this is exactly what I was looking for. $\endgroup$
    – Karagounis Z
    Nov 1, 2020 at 19:54

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