Klasy wykresów z łatwym cyklem hamiltonowskim, ale z TSP NP-twardym

13

Hamiltona Cykl Problem (HC) polega na znalezieniu cykl, który przechodzi przez wszystkie wierzchołki w danym undirected wykresu. Problem komiwojażera (TSP), polega na znalezieniu się cykl, który przechodzi przez wszystkie wierzchołki w danej krawędzi wykresu ważonych minimalizuje całkowitą odległość, mierzoną przez sumę mas krawędzi w cyklu. HC jest szczególnym przypadkiem TSP i oba są znane jako NP-zupełne [Garey i Johnson]. (Zobacz powyższe linki, aby uzyskać więcej szczegółów i wariantów tych problemów.)

Czy są jakieś przebadane klasy wykresów, na których problem cyklu Hamiltoniana można rozwiązać w czasie wielomianowym za pomocą nietrywialnego algorytmu, ale problem wędrownego sprzedawcy jest trudny do przeprowadzenia?

Nie trywialne jest wykluczenie klas, takich jak klasa pełnych grafów, w których cykl Hamiltonian gwarantuje istnienie i można je łatwo znaleźć, lub ogólnie klas grafów, w których zawsze istnieje gwarancja, że ​​HC.

cc.complexity-theory np-hardness hamiltonian-paths tsp graph-classes Standa Zivny
źródło

Odpowiedzi:

20

Cografy nie zawsze są hamiltonowskie, mają wielomianowe testy czasowe na Hamiltoniczność i są trudne do rozwiązania dla problemu podróżnego sprzedawcy.

Mówiąc bardziej ogólnie, problem cyklu hamiltonowskiego można rozwiązać w czasie wielomianowym (ale nie jest to możliwy do ustalenia parametr stały) na wykresach ograniczonej szerokości kliki ; patrz np. Fomin i in., „Szerokość kliki: od ceny ogólności”, SODA'09. Ale znowu, ponieważ te rodziny wykresów zawierają pełne wykresy, TSP jest trudny na tych wykresach.

David Eppstein
źródło
Ciekawi mnie twoje ostatnie zdanie. Czy to dlatego, że trasa TSP skutecznie identyfikuje kliki, ponieważ wszystkie wierzchołki kliki są przylegające do trasy?
Suresh Venkat,
1
Nie, chodzi mi po prostu o to, że TSP jest trudne nawet na pełnym wykresie, a pełne wykresy należą do wykresów z ograniczoną szerokością kliki. Same kompletne wykresy nie stanowią dobrej odpowiedzi na pytanie, ponieważ Hamiltoniczność jest dla nich trywialna, ale nadklasy klik (takie jak kartografy) mogą mieć nietrywialne, ale wielomianowe testy Hamiltonicity.
David Eppstein,
11

Co powiesz na pełne wykresy ? Ponieważ TSP zawsze można zredukować do wystąpienia na kompletnych wykresach (przez dodanie odpowiednich odległości między krawędziami), nadal trudno jest rozwiązać TSP na kompletnych wykresach. Ale wszelkie kompletne wykresy są hamiltonowskie.

Hsien-Chih Chang 張顯 之
źródło
Tak, oczywiście, dziękuję! Zapomniałem wykluczyć pełne wykresy, a w tym przypadku wszystkie klasy wykresów, w których HC jest trywialny.
Standa Zivny,
3
@Standa Zivny: Nie jestem pewien, czy zamierzasz edytować pytanie, czy nie, ale jeśli chcesz wykluczyć „wszystkie klasy wykresów, w których HC jest trywialnie rozwiązywalny”, powinieneś edytować pytanie. Wątpię jednak, aby możliwe było sformułowanie rozróżnienia między przypadkiem, w którym HC można rozwiązać „łatwo”, a przypadkiem, w którym HC można rozwiązać „trywialnie”.
Tsuyoshi Ito,
@Tsuyoshi Ito: Dobrze, że zredagowałem pytanie.
Standa Zivny,
@StandaZivny - Nie wszystkie wykresy, które są trywialne dla HC, są trudne dla TSP, np. Wykresy ścieżek.
RB
3

Istnieje wiele nieskończonych klas grafów, o których wiadomo, że mają obwody hamiltonowskie. Dwie szczególnie interesujące klasy to n-kostki i wykresy Halina. Jednym ze sposobów myślenia na wykresach Halina jest osadzenie drzewa o co najmniej 3 wierzchołkach, które nie mają wierzchołków wartościowości dwa w płaszczyźnie, a następnie przejście prostego obwodu przez 1-wartościowe wierzchołki drzewa.

http://en.wikipedia.org/wiki/Halin_graph

Wiadomo, że wykresy te mają HC i w rzeczywistości są albo trzustkowe (obwody wszystkich długości), albo nie mają dokładnie jednej długości obwodu, która musi być równej długości.

Joseph Malkevitch
źródło