Casos especiais de TSP gráfico

9

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:GGG

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?

Shiva Kintali
fonte

Respostas:

10

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

Christian Sommer
fonte
4

knkkkkkpoly(n,kk)k

Kunal
fonte