1
$\begingroup$

My lecture notes for $T$-joins states:

If $T = V$ then $T$ -joins of cardinality $V/2$ are exactly the perfect matchings of $G$ = $(V ,E)$. So, the minimum weight perfect matching problem can be reduced to the minimum weight $T$ -join problem by adding a large constant to each edge weight (to get a degree of 1 for each vertex in a $T$-join.)

I agree with this but I don't see how adding a large constant to each edge weight restricts the degree of each vertex to 1 in the $T$-join.

$\endgroup$

1 Answer 1

1
$\begingroup$

Since the algorithm is adding a large positive weight to each edge, the minimum weight $T$-join will have the minimum number of edges in it. Note that the least number of edges in a $T$-join for $T = V$ could be $|V|/2$. That is, each vertex has degree exactly $1$.

$\endgroup$
3
  • $\begingroup$ How does adding a large constant gaurantee that the $T$-join has the minimum number of edges in it? $\endgroup$ May 22, 2023 at 20:05
  • 1
    $\begingroup$ @SVMteamsTool Suppose you add constant $c \gg |E| \cdot max_{e \in E} \{ w_e \}$, then any $T$-join with $k+1$ edges will have larger weight than any $T$-join with $k$ edges. Can you prove this statement? $\endgroup$ May 22, 2023 at 20:09
  • $\begingroup$ Yes! That puts things into context, thanks! $\endgroup$ May 22, 2023 at 20:44

Your Answer

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

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