Abstract
Given an undirected graph G = (V, E) with a weight function c is an element of R-E, and a positive integer K, the Kth Traveling Salesman Problem ( Kth TSP) is to find K Hamilton cycles H-1, H-2, ..., H-K such that, for any Hamilton cycle H is not an element of {H-1, H-2, ..., H-K}, we have c(H) >= c(H-i), i = 1, 2, ..., K. This problem is NP-hard even for K fixed. We prove that Kth TSP is pseudopolynomial when TSP is polynomial.