Is Determination of the Travelling Salesman Tour an NP Hard Problem? Some Polynomial Time Reconstruction Approaches
Elias Munapo, Santosh Kumar, Philimon Nyamugure, Trust Tawanda · River Publishers eBooks · 2025
The minimum travelling salesman problem has attracted lot of attention as it has many industrial applications and computationally, it has been classified as NP hard. Algorithms have been developed and many situations have been successfully resolved. In this Chapter, we establish that at least in some cases, the minimum travelling salesman tour is not an NP hard problem. This conclusion is based on two different approaches, discussed in this chapter. First approach involves developing a binary variable mathematical model for the travelling salesman problem, adding some sub-tour elimination constraints, which are also functions of binary variables, and finally transforming that model as a quadratic programming program and solve that model by the interior point linear programming approach. The second approach uses the minimum spanning tree of a given network and converts that spanning tree into a node index restricted spanning tree and finally obtain the minimum salesman tour. In this approach, finally, we establish that the index restricted spanning tree is equivalent to the minimum travelling salesman tour.