Content: The Christofides algorithm finds a minimum spanning tree, then finds all the odd degree vertices, and adds extra edges using a minimum weight bipartite matching on those odd vertices to make all of them even, so that a Eulerian tour can be found (since all vertices are even now).

My question arises from a simple example: suppose there are four odd-degree vertices in the MST, labeled $v_1, ..., v_4$. Now suppose that $v_3$ and $v_4$ are already connected in the original MST, and further suppose that the minimum weight matching requires them to be connected. This means that the matching is redundant, and the two vertices still have odd degree at the end.

Does this simply mean that the bipartite matching has to be re-run to find the "next-to-minimum" matching, or are there other heuristics?

  • $\begingroup$ No, you just continue with the algorithm as usual. $\endgroup$ – Yuval Filmus Oct 31 '15 at 8:18
  • $\begingroup$ Consider also what happens if there are exactly two odd-degree vertices, and they're connected. $\endgroup$ – Yuval Filmus Oct 31 '15 at 11:33
  • $\begingroup$ I see one way to "continue with the algorithm as usual". Since the next step is the construction of the Euler tour, all vertices must have even degree, therefore the two odd-degree vertices that already had an edge in the MST must be assigned an extra edge. This prevents the euler tour from getting stuck, and the extra edge doesn't matter in the end because the algorithm takes shortcuts in the final step. $\endgroup$ – yjc Oct 31 '15 at 18:50
  • $\begingroup$ That's right. Parallel edges are simply allowed. $\endgroup$ – Yuval Filmus Oct 31 '15 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.