<p>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$.</p>

CC BY-SA 3.0
2012-04-03T03:48:35.737Z
2012-04-03T03:48:35.737Z
Kunal
<p>Take a look at Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk, "<a href="http://arxiv.org/abs/1103.0534" rel="nofollow">Solving connectivity problems parameterized by treewidth in single exponential time</a>", 2011.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-03T07:30:27.147Z
2012-04-03T21:20:50.093Z
2012-04-03T21:20:50.093Z
Andreas Björklund
<p>As far as I know, dynamic programming does the trick</p>

<p>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). </p>

<p>Philip N. Klein: <a href="http://dx.doi.org/10.1137/060649562">A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights</a>. SIAM J. Comput. 37(6): 1926-1952 (2008)
(<a href="http://www.cs.brown.edu/~klein/publications/no-contraction.pdf">PDF on Philip Klein's website</a>)</p>

<p>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).</p>

<p>Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: <a href="http://dx.doi.org/10.1007/s00493-010-2341-5">Approximation algorithms via contraction decomposition</a>. Combinatorica 30(5): 533-552 (2010)
(<a href="http://erikdemaine.org/papers/ContractionTSP_Combinatorica/">Paper on Erik Demaine's website</a>)</p>

<p>Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: <a href="http://doi.acm.org/10.1145/1993636.1993696">Contraction decomposition in H-minor-free graphs and algorithmic applications</a>. STOC 2011: 441-450</p>

<p>For videos on these PTAS constructions, see <a href="http://courses.csail.mit.edu/6.889/fall11/lectures/L15.html">Planar TSP</a> and <a href="http://courses.csail.mit.edu/6.889/fall11/lectures/L23.html">Minor-free TSP</a> (again not focussing on the tree-width part). </p>

CC BY-SA 3.0
2012-04-03T03:51:06.057Z
2012-04-03T03:51:06.057Z
Christian Sommer
<p>In <strong>Graphic TSP</strong>, you are given an unweighted undirected graph $G$ and the goal is to find a shortest tour in $G$ that visits every vertex <em>at least once</em>. Note that this is NOT same as finding a hamiltonian circuit in $G$. My questions are :</p>

<blockquote>
  <p>What is the complexity of Graphic TSP on bounded treewidth graphs ?</p>
</blockquote>

<p>Are there any special cases of Graphic TSP with non-trivial polynomial-time algorithms ?</p>

<ds.algorithms><treewidth><tsp>
Special cases of Graphic TSP
Shiva Kintali
# Special cases of Graphic TSP

(Asked by: username_0 on 2012-04-03)

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 ?

**Tags:** ds.algorithms, treewidth, tsp

---

## 3 answers

### Answer by username_3 on 2012-04-03. Score: 10 | Accepted answer

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](http://dx.doi.org/10.1137/060649562). SIAM J. Comput. 37(6): 1926-1952 (2008)
([PDF on Philip Klein's website](http://www.cs.brown.edu/~klein/publications/no-contraction.pdf))

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](http://dx.doi.org/10.1007/s00493-010-2341-5). Combinatorica 30(5): 533-552 (2010)
([Paper on Erik Demaine's website](http://erikdemaine.org/papers/ContractionTSP_Combinatorica/))

Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: [Contraction decomposition in H-minor-free graphs and algorithmic applications](http://doi.acm.org/10.1145/1993636.1993696). STOC 2011: 441-450

For videos on these PTAS constructions, see [Planar TSP](http://courses.csail.mit.edu/6.889/fall11/lectures/L15.html) and [Minor-free TSP](http://courses.csail.mit.edu/6.889/fall11/lectures/L23.html) (again not focussing on the tree-width part).


---

### Answer by username_1 on 2012-04-03. Score: 4

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$.


---

### Answer by username_2 on 2012-04-03. Score: 4

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](http://arxiv.org/abs/1103.0534)", 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.


---

