Discuss the relation between minimal spanning trees of Kn and minimal s-trees. In particular, find a condition on s which guaranteesthat a given minimal spanning tree of Kn extends to a minimal s-tree. Showthat the strategy for selecting s which we have used in Example 15.2.4 doesnot always lead to a good bound.Balas and Toth calculated the s-tree relaxation as well during their examinationof the assignment relaxation. On average, w(MsT) was only 63%of w(TSP), which is considerably worse than w(AP). This may be explainedby the fact that the number of s-trees is much larger than the number ofpermutations without fixed points.