Polynomial Reduction of TSP to Freely Open-loop TSP

Abstract

Travelling Salesman Problem (TSP) is one of the earliest combinatorial problem that is identified to be NP-hard problem. It is a problem that seeks to find the shortest possible route in a graph problem which passes through all nodes only once and return to the starting point. A variant of TSP is the Freely Open-loop TSP (FOTSP) which seeks to find the shortest route in the graph without having to return to starting point and with no specific starting or end node. In this paper, a reduction of polynomial complexity for TSP problem into FOTSP is presented and vice versa. This reduction proves that FOTSP is also NP-complete just as TSP. © 2019 IEEE.