<p>TSP is the optimization version of HAMILTONIAN CYCLE, which can be expressed by an MSO-formula (Monadic Second-Order Logic) with edge-set quantifications ($MSO_2$, also known as MSO in the incidence-graph model) as follows:  Let $hamilton(F)$ express that $F$ is a set of edges of the input graph $G = (V, E)$ such that every vertex is incident to exactly two edges in $F$, and additionally $F$ is connected.   Then
$$\min_{F \subseteq E} \{ \sum_{e \in F} w(e) : G \models hamilton(F)\},$$
where $w(e)$ denodes the weight of an edge $e$.  Hence, TSP is a Linear MSO-definable Optimization problem.   Via <a href="http://dblp.uni-trier.de/rec/bibtex/journals/iandc/Courcelle90">Courcelle's</a> <a href="http://dblp.uni-trier.de/rec/bibtex/journals/tcs/CourcelleM93">Theorem</a>, TSP can therefore be solved  in linear time on graphs of bounded treewidth (for example, using dynamic programming as mentioned by Andrew in the comment above). </p>

CC BY-SA 3.0
2011-12-17T16:39:39.253Z
Alexander I downvoted you because I didn't see "Additionally F is connected" After I see that, I try to remove downvote but I see I can't, I'd edited your answer to do this, but currently I'm waiting someone peer review it. anyway, really I'm not good in logic, and too many things are question for me, but, except converting this to some finite automata  is there any elegant way? For example O(f(k)*n)? because automata parses input string in $O(n^3)$ not O(n).
Saeed
CC BY-SA 3.0
2011-12-17T17:48:33.217Z
You can also use a somewhat standard dynamic programming on the tree-decomposition as mentioned by Andrew D. King.  Roughly, you'd store in a table all ways the ham-cycle could "cross" the current bag (all "path fragments", i.e., all entry-exit points etc), and for each of such entries, the minimum weight of all partial solutions having this particular set of path fragments.  This will give you a running time of roughly $O(kˆ{O(k)}n)$.
Alexander Langer
CC BY-SA 3.0
2011-12-17T17:57:41.810Z
See, e.g., http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 on page 17ff for details.
Alexander Langer
CC BY-SA 3.0
2011-12-17T20:37:35.803Z
Thanks, I think it's better to move your comment in your answer, because main answer was in your comment :).
Saeed
CC BY-SA 3.0
2011-12-17T12:18:22.670Z
2011-12-17T17:59:45.333Z
2011-12-17T17:59:45.333Z
Alexander Langer
<p>I see there are some papers/thesis which says TSP is solvable in $O(n)$ in bounded tree-width graphs and some of them implicitly refer to Cook and Seymour (not exact paper just said that they solve it), but I can't find any paper about it.</p>

<p>All the things I can find is branch-decomposition based algorithms with merging techniques, which are all heuristic (e.g <a href="http://web.eecs.utk.edu/~langston/projects/papers/tmerge.pdf" rel="nofollow">very nice heuristic</a>) but non of them are exact algorithm. Does anyone know the related papers for linear time solution? Or paper which says is impossible? or probably impossible? (any good news bad news, its not 3in1 question:).</p>

CC BY-SA 3.0
2011-12-17T12:16:00.763Z
Can't this be solved with a standard dynamic programming approach?  You will want to encode, for each bag of the decomposition, for all sets of entry/exit to the subtree, what the best route is.
Andrew D. King
<cc.complexity-theory><reference-request><graph-theory><treewidth>
TSP in bounded tree-width (or bounded branch width) graphs
Saeed
# TSP in bounded tree-width (or bounded branch width) graphs

(Asked by: username_0 on 2011-12-16)

I see there are some papers/thesis which says TSP is solvable in $O(n)$ in bounded tree-width graphs and some of them implicitly refer to Cook and Seymour (not exact paper just said that they solve it), but I can't find any paper about it.

All the things I can find is branch-decomposition based algorithms with merging techniques, which are all heuristic (e.g [very nice heuristic](http://web.eecs.utk.edu/~langston/projects/papers/tmerge.pdf)) but non of them are exact algorithm. Does anyone know the related papers for linear time solution? Or paper which says is impossible? or probably impossible? (any good news bad news, its not 3in1 question:).

**Tags:** cc.complexity-theory, reference-request, graph-theory, treewidth
> **Comments:**
> **username_1**: Can't this be solved with a standard dynamic programming approach?  You will want to encode, for each bag of the decomposition, for all sets of entry/exit to the subtree, what the best route is.  

---

## 1 answers

### Answer by username_2 on 2011-12-17. Score: 12 | Accepted answer

TSP is the optimization version of HAMILTONIAN CYCLE, which can be expressed by an MSO-formula (Monadic Second-Order Logic) with edge-set quantifications ($MSO\_2$, also known as MSO in the incidence-graph model) as follows: Let $hamilton(F)$ express that $F$ is a set of edges of the input graph $G = (V, E)$ such that every vertex is incident to exactly two edges in $F$, and additionally $F$ is connected. Then
$$\min\_{F \subseteq E} \{ \sum\_{e \in F} w(e) : G \models hamilton(F)\},$$
where $w(e)$ denodes the weight of an edge $e$. Hence, TSP is a Linear MSO-definable Optimization problem. Via [Courcelle's](http://dblp.uni-trier.de/rec/bibtex/journals/iandc/Courcelle90) [Theorem](http://dblp.uni-trier.de/rec/bibtex/journals/tcs/CourcelleM93), TSP can therefore be solved in linear time on graphs of bounded treewidth (for example, using dynamic programming as mentioned by Andrew in the comment above).

> **Comments:**
> **username_0**: Alexander I downvoted you because I didn't see "Additionally F is connected" After I see that, I try to remove downvote but I see I can't, I'd edited your answer to do this, but currently I'm waiting someone peer review it. anyway, really I'm not good in logic, and too many things are question for me, but, except converting this to some finite automata  is there any elegant way? For example O(f(k)*n)? because automata parses input string in $O(n^3)$ not O(n).  
> **username_2**: You can also use a somewhat standard dynamic programming on the tree-decomposition as mentioned by Andrew D. King.  Roughly, you'd store in a table all ways the ham-cycle could "cross" the current bag (all "path fragments", i.e., all entry-exit points etc), and for each of such entries, the minimum weight of all partial solutions having this particular set of path fragments.  This will give you a running time of roughly $O(kˆ{O(k)}n)$.  
> **username_2**: See, e.g., http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 on page 17ff for details.  
> **username_0**: Thanks, I think it's better to move your comment in your answer, because main answer was in your comment :).  

---

