Casos especiais de TSP gráfico

No TSP gráfico , você recebe um gráfico não direcionado não ponderado e o objetivo é encontrar um passeio mais curto em G que visite todos os vértices pelo menos uma vez . Note-se que este não é o mesmo que encontrar um circuito hamiltoniano em G . Minhas perguntas são:$G$$G$$G$

Qual é a complexidade do TSP gráfico em gráficos de largura de árvore limitada?

Existem casos especiais de TSP gráfico com algoritmos de tempo polinomial não triviais?

Até onde eu sei, a programação dinâmica faz o truque

O artigo de Klein sobre TSP para gráficos planares tem os detalhes para gráficos planares com largura de árvore delimitada. Se o gráfico não for plano, o programa dinâmico é mais lento (a dependência na largura da árvore é pior).

Philip N. Klein: Um esquema de aproximação em tempo linear para TSP em gráficos planares não direcionados com pesos de borda . SIAM J. Comput. 37 (6): 1926-1952 (2008) ( PDF no site de Philip Klein )

A programação dinâmica também é usada para obter um PTAS para gráficos de gênero limitado e sem menores (mas, até onde me lembro, os autores não especificam os detalhes do PD).

Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: algoritmos de aproximação via decomposição de contração . Combinatorica 30 (5): 533-552 (2010) (Artigo no site de Erik Demaine )

Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: Decomposição da contração em gráficos livres de H-minor e aplicações algorítmicas . STOC 2011: 441-450

Para vídeos sobre essas construções de PTAS, consulte TSP Planar e TSP sem Menor (novamente sem focar na parte da largura da árvore).

$k$$n$$k^k$$k$$k^k$$poly(n, k^k)$$k$

Dê uma olhada em Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk, " Resolvendo problemas de conectividade parametrizados pela largura da árvore em tempo exponencial único ", 2011.

$\mbox{poly}(n)2^{O(k)}$$k$$n$