On the Relation Between the Traveling-Salesman and the Longest-Path Problems

Abstract

The main result of this paper is that the traveling-salesman problem is a special case of the longest-path problem. Two formulations of the traveling-salesman problem are considered, the version in which the salesman visits each city exactly once and the more general formulation in which each city may be visited more than once. Both cases are reduced to the problem of finding the longest path between two nodes in a finite, connected graph. The remainder of the paper is then devoted to possible algorithms for the longest-path problem, since none presently exist.