MSTs in Christofides Algorithm

Question

I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST_1$ and $MST_2$ where both are Minimum Spanning Trees, because $G$ contains more than one edge with the same weight.

In image [2] below, the difference between $MST_1$ and $MST_2$ is basically the $Arlington \to Somerville$ or $Arlington \to Belmont$ (or vice-versa) connection. Depending on the internal representation of the graph, whether a adjacency matrix or list, this could happen by just altering which node will be the first, e.g. if $Arlington$ will be processed earlier than $Somerville$.

The difference of dealing with one or the other, is the next steps of Christofides algorithm, that requires to apply the Minimum-Weight Perfect Matching algorithm on the odd nodes.

The $MST_1$ has only $4$ odd nodes and the perfect matching result is $Arlington \to Medford$ and $Cambridge \to Everett$, which I will call $MWPF_1$. The $MST_2$ has $6$ nodes and the perfect matching result is $Arlington \to Medford$, $Somerville \to Everett$ and $Belmont \to Cambridge$, which I will call $MWPF_2$.

The next step from Christofides is to merge both edges from $MST$ with the ones from perfect matching.

Now, if we choose to merge both $MST_1$ and $MWPF_1$, we will end up with nodes only with even degrees that's what we want as the next step is to calculate the Eulerian Circuit.

But, if we choose $MST_2$ and $MWPF_2$, we will end up with only one new edge, as other two are already present ($Somerville \to Everett$ and $Belmont \to Cambridge$) in $MST_2$. The result then will be $4$ odd vertices and no possible Eulerian Circuit can be generated out of this merge!

How this should be dealt in Christofides algorithm? Should all the $MSTs$ generated from one graph to be tried out?

Answer 1

The important thing to note is that when merging the MST and the Matching, you create a multigraph. This means even when you merge, even if there are edges that already exist, you add them anyway. So you will always end up with even degree vertices.

This is step 4 of the algorithm as seen on Wikipedia.

So in your second case, you now have a multigraph where edges $(Somerville \rightarrow Everett)$ and $(Belmont \rightarrow Cambridge)$ each show up twice.

Answer 2

The analysis of Christofides' algorithm works for any MST. Hence any MST will get you the approximation guarantee of the algorithm.

More generally, if you really had to try out all possible MSTs, then the resulting algorithm wouldn't run in polynomial time, sine there could potentially be exponentially many MSTs.