Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
In Graphic TSP, you are given an unweighted undirected graph $G$ and the goal is to find a shortest tour in $G$ that visits every vertex at least once. Note that this is NOT same as finding a hamiltonian circuit in $G$. My questions are :
What is the complexity of Graphic TSP on bounded treewidth graphs ?
Are there any special cases of Graphic TSP with non-trivial polynomial-time algorithms ?
As far as I know, dynamic programming does the trick
Klein's paper on TSP for planar graphs has the details for planar graphs with bounded tree-width. If the graph is not planar, the dynamic program is slower (dependency on the tree-width is worse).
Philip N. Klein: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. SIAM J. Comput. 37(6): 1926-1952 (2008) (PDF on Philip Klein's website)
Dynamic programming is also used to obtain a PTAS for bounded-genus and minor-free graphs (but as far as I remember the authors do not specify the details of the DP).
Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: Approximation algorithms via contraction decomposition. Combinatorica 30(5): 533-552 (2010) (Paper on Erik Demaine's website)
Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: Contraction decomposition in H-minor-free graphs and algorithmic applications. STOC 2011: 441-450
For videos on these PTAS constructions, see Planar TSP and Minor-free TSP (again not focussing on the tree-width part).
I believe for treewidth-$k$ graphs, the problem is exactly solvable in time polynomial in $n$ and $k^k$. This is true also for the metric problem on weighted bounded treewidth graphs. One does a dynamic program, where for each bag, you have an entry for every possible way of crossing from one side of the bag to the other. With $k$ nodes in the bag, one has at most $k^k$ possible configurations of going from one side of the bag to the other. In fact this works for any graph family which can be partitioned using small vertex separators into components belonging to the family (and thus in particular having small vertex separators themselves). The running time would be $poly(n, k^k)$ if the separators are of size $k$.
Take a look at Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk, "Solving connectivity problems parameterized by treewidth in single exponential time", 2011.
I think you can use their ideas to get a randomized $\mbox{poly}(n)2^{O(k)}$ time algorithm for treewidth-$k$ graphs on $n$ vertices.
