Sonderfälle von Graphic TSP

In Graphic TSP erhalten Sie einen ungewichteten ungerichteten Graphen und das Ziel ist es, eine kürzeste Tour in , die jeden Scheitelpunkt mindestens einmal besucht . Beachten Sie, dass dies NICHT mit dem Auffinden einer Hamilton-Schaltung in identisch ist . Meine Fragen sind:G $G$$G$$G$

Wie komplex ist Graphic TSP in Graphen mit begrenzter Baumbreite?

Gibt es spezielle Fälle von grafischem TSP mit nicht trivialen Polynom-Zeit-Algorithmen?

Soweit ich weiß, reicht die dynamische Programmierung aus

Kleins Artikel über TSP für planare Graphen enthält die Details für planare Graphen mit begrenzter Baumbreite. Wenn der Graph nicht planar ist, ist das dynamische Programm langsamer (die Abhängigkeit von der Baumbreite ist schlechter).

Philip N. Klein: Ein lineares Zeitnäherungsschema für TSP in ungerichteten planaren Graphen mit Kantengewichten . SIAM J. Comput. 37 (6): 1926-1952 (2008) ( PDF auf der Website von Philip Klein )

Dynamische Programmierung wird auch verwendet, um ein PTAS für Graphen mit begrenzter Gattung und ohne Moll zu erhalten (soweit ich mich erinnere, geben die Autoren die Details des DP nicht an).

Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: Approximationsalgorithmen durch Kontraktionszerlegung . Combinatorica 30 (5): 533-552 (2010) (Artikel auf der Website von Erik Demaine )

Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: Kontraktionszerlegung in h-Moll-freien Graphen und algorithmischen Anwendungen . STOC 2011: 441 & ndash; 450

Videos zu diesen PTAS-Konstruktionen finden Sie unter Planar-TSP und Minor-free-TSP (wiederum ohne Fokus auf den Teil mit der Baumbreite ).

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

Werfen Sie einen Blick auf Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk, " Lösen von Verbindungsproblemen durch Baumweite in einzelnen exponentiellen Zeit parametriert " 2011.

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