# Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

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)

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

This is starting to get confusing ## Step 4 - Construct a minimum-weight perfect matching $$M$$ in this subgraph ## Step 5 - Unite matching and spanning tree $$T$$ and $$M$$ to form an Eulerian multigraph ## 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: • Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution. – Yuval Filmus Nov 27 '18 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 '18 at 21:46
• I’m not going to check your solution. I can help you with any conceptual difficulties. – Yuval Filmus Nov 27 '18 at 21:49

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 '18 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 '18 at 12:32
• 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. – John L. Dec 2 '18 at 12:43
1. It's an approximation algorithm, so the answer can be suboptimal.
2. The answer of a given TSP is a Hamiltonian cycle, NOT Eulerian path.

But the above doesn't justify that you have a wrong result, because simply:

1. You forgot the last step, which is short-cutting -- removal of repeated vertices.

So because you have two paths ($$A \alpha B$$ and $$G \alpha H$$) with repeated $$\alpha$$, you should modify one of those. For example -- make a short-cut (and skip $$\alpha$$) when travelling from $$G$$ to $$H$$ and go directly with your upper red edge. Then you'll have a valid solution to this problem.

EDIT: Jack has pointed out (correctly) that you didn't create a minimum spanning tree. However, if we suppose that the tree is correct (for example the cost of $$GH$$ edge is 56) and you get the result as seen above, then my rules still apply.