Hello,

I posted this question to the Computer Science forum, but the focus there seems to be more on software and systems. Perhaps Mathematics is a more appropriate place for algorithms/theoretical computer science topics. If you think there is a better forum for this post, please let me know. And now for my question...

Can the Traveling Salesman Problem (TSP) be solved in sub-exponential time when restricted to graphs with bounded treewidth? Arnborg and Proskurowski (1989, citation below) gave a linear-time algorithm for Hamiltonian Circuit 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.