Specjalne przypadki graficzne TSP

W Graphic TSP otrzymujesz nieważony niekierowany wykres$G$ a celem jest znalezienie najkrótszej trasy w $G$który odwiedza każdy wierzchołek przynajmniej raz . Zauważ, że NIE jest to to samo, co znalezienie obwodu hamiltonowskiego$G$. Moje pytania to:

Jaka jest złożoność Graphic TSP na ograniczonych wykresach szerokości?

Czy są jakieś specjalne przypadki Graficznego TSP z nietrywialnymi algorytmami czasu wielomianowego?

O ile mi wiadomo, programowanie dynamiczne załatwia sprawę

Artykuł Kleina na temat TSP dla grafów planarnych zawiera szczegółowe informacje dla grafów planarnych z ograniczoną szerokością drzewa. Jeśli wykres nie jest płaski, program dynamiczny działa wolniej (zależność od szerokości drzewa jest gorsza).

Philip N. Klein: Schemat aproksymacji w czasie liniowym dla TSP w niekierowanych grafach planarnych z wagami krawędzi . SIAM J. Comput. 37 (6): 1926-1952 (2008) ( PDF na stronie internetowej Philipa Kleina )

Programowanie dynamiczne jest również używane do uzyskania PTAS dla grafów z ograniczonym rodzajem i drugorzędnych grafów (ale o ile pamiętam autorzy nie określają szczegółów DP).

Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: Algorytmy aproksymacyjne poprzez rozkład skurczu . Combinatorica 30 (5): 533-552 (2010) ( artykuł na stronie internetowej Erika Demaine'a )

Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: Rozkład skurczu w grafach wolnych od H-moll i zastosowaniach algorytmicznych . STOC 2011: 441–450

Filmy na temat tych konstrukcji PTAS, zobacz Planar TSP i Minor-free TSP (ponownie nie koncentrując się na części o szerokości drzewa).

Wierzę w treewidth-$k$ wykresy, problem jest dokładnie rozwiązywalny w wielomianie czasowym w $n$ i $k^k$. Dotyczy to również problemu metrycznego na ważonych wykresach szerokości poprzecznej. Jeden wykonuje program dynamiczny, w którym dla każdej torby masz wejście na każdy możliwy sposób przejścia z jednej strony torby na drugą. Z$k$ węzły w torbie, co najwyżej jeden $k^k$możliwe konfiguracje przechodzenia z jednej strony torby na drugą. W rzeczywistości działa to dla dowolnej rodziny grafów, które można podzielić za pomocą małych separatorów wierzchołków na komponenty należące do rodziny (a tym samym same w sobie same małe separatory wierzchołków). Czas trwania byłby$poly(n, k^k)$ jeśli separatory są wielkości $k$.

Spójrz na Marka Cygana, Jespera Nederlofa, Marcina Pilipczuka, Michała Pilipczuka, Johana van Rooija, Jakuba Onufrego Wojtaszczyka: „ Rozwiązywanie problemów z łącznością sparametryzowanych przez szerokość w czasie wykładniczym ”, 2011.

Myślę, że możesz wykorzystać ich pomysły, aby uzyskać randomizację $\mbox{poly}(n)2^{O(k)}$ algorytm czasu dla szerokości$k$ wykresy włączone $n$ wierzchołki.