I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)

  • $\alpha$ denotes the start and end vertex of the Eulerian path enter image description here

Step 1 - Calculate minimum spanning tree $T$

enter image description here enter image description here


Step 2 - Calculate the set of verices $O$ with odd degree in $T$

enter image description here enter image description here


Step 3 - Form the subgraph of $G$ using only the vertices of $O$

This is starting to get confusing

enter image description here

enter image description here enter image description here


Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph

enter image description here


Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph

enter image description here


I am NOT satisfied

Did I do something wrong or did I simply just hit an sub-optimal solution. It is not hard to see that the Eulerian path easily could be improved by either connection $G \rightarrow H$ or $A \rightarrow B$ as illustrated underneath:

enter image description here

  • Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution. – Yuval Filmus Nov 27 at 21:07
  • @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right? – Sebastian Nielsen Nov 27 at 21:46
  • I’m not going to check your solution. I can help you with any conceptual difficulties. – Yuval Filmus Nov 27 at 21:49
up vote 5 down vote accepted

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of

On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$\alpha$ should be replaced by edge HG.

  • Yes, thank you a lot! This is the error I had trouble finding! – Sebastian Nielsen Nov 28 at 8:40
  • question: I was supposed to end up with an Euler path, however, that is not the case, since not every edge of g is visited exactly once, there is a lot of edges that is not visited at all! Can I still call it an Euler path, or why didn't I end up with an Euler path? – Sebastian Nielsen Dec 2 at 12:32
  • 1
    Checking ... just a minute or two ... – Apass.Jack Dec 2 at 12:34
  • 1
    The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem (TSP). It uses Euler path of a temporary graph to find a hamiltonian circuit of the original graph that approximates the optimal solution to TSP. So you are not supposed to end up with a Euler path. You should end up with a hamiltonian circuit, a cycle that visits every vertex of the original graph exactly once. – Apass.Jack Dec 2 at 12:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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