2
$\begingroup$

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) 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:).

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Andrew D. King
    Dec 17, 2011 at 12:16

1 Answer 1

Reset to default
12
$\begingroup$

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 Theorem, 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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Dec 17, 2011 at 16:39
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Alexander Langer
    Dec 17, 2011 at 17:48
  • 2
    $\begingroup$ See, e.g., cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 on page 17ff for details. $\endgroup$
    – Alexander Langer
    Dec 17, 2011 at 17:57
  • $\begingroup$ Thanks, I think it's better to move your comment in your answer, because main answer was in your comment :). $\endgroup$
    – Saeed
    Dec 17, 2011 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.