Traveling Salesman Problem Under Categorization

We introduce two new classes of traveling salesman problems (TSP1 and TSP2) which subsume the classical traveling salesman problem and the bottleneck traveling salesman problem. It is shown that these problems are strongly NP-complete on Halin graphs eventhough their extreme cases (i.e. traveling salesman problem and bottleneck traveling salesman problem) are solvable in polynomial time on such graphs. It is also shown that TSP2 is solvable in polynomial time on Halin graphs if an associated parameter p is fixed, but TSP1 still remains NP-complete. For TSP2, a polynomial time (for fixed p) heuristic is suggested which produces a solution whose objective function value is no worse than twice that of the optimal solution whenever the underlying graph is complete, undirected and edge weights satisfy the triangle inequality.