Predicting the difficulty of TSP instances using MST

The efforts needed to solve travelling salesman problems (TSP) obviously depend on the problem size. However, also other factors can predict the difficulty of a given problem instance. We present a measure based on the minimum spanning tree (MST). The measure counts the number of knot points, which branch the tree into multiple sub-trees. We show by experiments that the more there are knots in the tree, the more difficult the problem instance is to solve by both humans and computers.