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.