Thread: Complexity of Traveling Salesman Problem

Hello,

Does anyone know the complexity of the Traveling Salesman Problem (TSP) on graphs of bounded treewidth? Arnborg and Proskurowski (1989, citation below) gave a linear-time algorithm for Hamiltonian circuits on graphs with bounded treewidth. Can this be extended to TSP?

Thanks!


Reference:

Stefan Arnborg and Andrzej Proskurowski. Linear Time Algorithms for NP-Hard Problems Restricted to Partial k-trees. Discrete Applied Mathematics 23, pp. 11-24. 1989.