Weighted $K\_5$ have the unique property that their edge set can be interpreted as the disjoint union of their shortest and their longest Hamilton cycle.


That makes $K\_5$ attractive for designing new TSP heuristics; especially extremal $K\_5$ in TSP instances seem interesting for generating starting tours (e.g. the $K\_5$ with the longest shortest tour) for tour expansion heuristics.


Now as there are $\binom{n}{5}$ $K\_5$ in a TSP instance with $n$ vertices, even the slightest speedup in calculating the optimal Hamilton cycle in a weighted $K\_5$ would be desirable, leading to the



> 
> **Question:**
> 
> 
> what is the minimal number of additions and comparisons that are necessary to determine the edge-set of a shortest Hamilton cycle in a weighted $K\_5$?
> 
> 
> 



Fastest algorithm for calculating optimal tours in weighted $K_5$
OK, I guess I have exhausted my ideas, so I'll make a claim on 14 additions and 8 (actually 7 and a half in a certain sense) comparisons.


Let A,B,C,D,E be the vertices of the pentagon. Consider all cycles that contain the edge AB (there are 6 of them and the other 6 are their complements, so if I find *both* the shortest and the longest of these six cycles, I'll have just to compute the weight of the shortest and the weight of the complement of the longest one and to compare them to reach the final conclusion.


Now compute X=BC+DE, Y=BD+CE, Z=BE+CD and x=DE+AC, y=CE+AD, z=CD+AE (6 additions). Note that to make a cycle, we can combine any small letter with any capital one *provided that they are different*. Thus we have to find the minimum and the maximum of
x+Z, x+Y; y+X, y+Z; z+Y, z+X; Note that we can make the comparison in each pair between ; with the common small letter without knowing the sums to select 3 candidates for the minima and 3 for the maxima and it cannot happen that the splitting will be into the set of the first elements in each pair and the set of the second ones (because the sums are equal). Thus, after 3 comparisons (actually 2 and a half because the first two determine the outcome of third one with probability 1/2 on random data), we will have something like x+Z, y+X, z+X for the minimum candidates and the complementary set for the maximum ones. Now let's find the minimum. Note that y+X and z+X can still be compared without computation, so we make this comparison, then compute the value of the smaller sum, compute the value of the remaining sum and compare the two (2 additions, 2 comparisons). Double that for finding the maximum and we see that we have spent 10 additions and 7 comparisons by the moment. Now the total weight of the minimal cycle can be found by adding the weight of AB (one addition) but the weight of the complement of the maximal one requires 3 additions (we have one of the sums X,Y,Z in it and need to add 3 extra edges. After we compute all that, we make the final comparison and we are done in (14,8) in the worst case scenario, as promised.


I would love to see someone to beat that (especially as far as the comparisons are concerned because the execution of the if(...)... ;else...; construct takes more time than the execution of a=b+c; command), so don't hurry to accept this answer!


