# Finding a minimum weight perfect matching in Christofides TSP algorithm

Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd vertices. N is even, so a bipartite matching is possible.

When the N odd-degree vertices are found, there are $n \choose \frac{n}{2}$ possible ways to split them into two sets. Does Christofides' algorithm really need to run a min-weight bipartite matching for all of these possible partitions? Or is there a better way?

I realize there is an approximate solution, which is to greedily match each vertex with another vertex that is closest to it. However, if the exact solution is to try all possible partitions, this seems inefficient.

• Usually when we talk about approximation algorithms, we are considering only efficient (polytime) algorithms. This one is no exception. – Yuval Filmus Oct 31 '15 at 9:14

• The standard blossom algorithm is applicable to a non-weighted graph. The last section on the wiki page says that the Blossom algorithm is only a subroutine if the goal is to find a min-weight or max-weight maximal matching on a weighted graph, and that a combinatorial algorithm needs to encapsulate the blossom algorithm. I haven't read the Kolmogorov paper yet, but the word "combinatorial" suggests that each possible partition of $N$ into two halves must be checked to get the min or max matching. – yjc Oct 30 '15 at 19:22