Co-NP-kompletność minimalnej trasy TSP?

18

Ten problem pojawił się w moim niedawnym poście na blogu , przypuśćmy, że masz wycieczkę po TSP, czy jest to zgodne z NP-kompletnym, aby ustalić, czy jest to minimalne?

Dokładniej jest następujący problem NP-zupełny:

Instancja: Biorąc pod uwagę pełny wykres G z krawędziami ważonymi dodatnimi liczbami całkowitymi i prosty cykl C, który odwiedza wszystkie węzły G.

Pytanie: Czy istnieje prosty cykl D, który odwiedza wszystkie węzły G w taki sposób, że całkowity ciężar wszystkich krawędzi D w G jest ściśle mniejszy niż całkowity ciężar wszystkich krawędzi C w G?

Lance Fortnow
źródło

Odpowiedzi:

17

Szkic możliwej redukcji, aby udowodnić, że jest kompletny NP.

Nieformalnie zaczyna się od zmodyfikowanej formuły 3SAT służącej do wykazania, że ​​3SAT jest kompletny z ASP (inny problem z rozwiązaniem) i „podąża” za standardowym łańcuchem redukcji 3SAT => BEZPOŚREDNI HAMCYCLE => BEZPOŚREDNI HAMCYCLE => TSP

  • Start z wzorem 3SAT φ z n zmiennych x1,...xn i m caluses C1,...,Cm ;
  • Trasformuj go do nowej formuły φ dodając nową zmienną t ...;
  • ... i rozszerzenie każdej klauzuli do ( x i 1x i 2x i 3t ) ;(xja1xja2)xja3))(xja1xja2)xja3)t)
  • Od budowydiamenty strukturawykres G = { V , E } celu udowodnienia, że DIRECTED Hamiltona cykl jest NP-zupełny; przypuszczać, że każdy punkt C J odpowiadają węzła N J w G ;φsol={V.,mi}dojotN.jotsol
  • Zmodyfikuj na wykres G = { V , E }, zastępując każdy węzeł trzema połączonymi węzłami i zmodyfikuj krawędzie zgodnie ze standardową redukcją zastosowaną w celu wykazania kompletności NP NIEZRÓŻNIONEGO CYKLU HAMILTONIANOWEGO z BEZPOŚREDNIEGO HAMILTONIAŃSKIEGO CYCLE tj. jest węzłem używanym do krawędzi przychodzących, jest węzłem używanym do krawędzi wychodzących;solsol={V.,mi}u 1 , u 2 , u 3 u 1 u 3uu1,u2),u3)u1u3)
  • Przekształć instancję NIEZBĘDNEGO CYKLU HAMILTONIAJSKIEGO na na instancję TSP w której wszystkie krawędzie mają wagę , z wyjątkiem (unikalnej) krawędzi diamentu przechodzącej na "dodatnie" przypisanie które ma masę (czerwona krawędź na poniższym rysunku); wreszcie krawędzie dodane w celu uzupełnienia mają ciężar . T G w = 1 t w = 2 G w = 3solT.solw=1tw=2)solw=3)

Oczywiście instancja TSP ma prosty cykl, który odwiedza wszystkie węzły, co odpowiada zadowalającemu przypisaniu w którym (i ta trasa może być łatwo skonstruowana w czasie wielomianowym), ale ma całkowitą wagę (ponieważ używa krawędzi odpowiadającej przypisaniu która ma wagę 2). ma kolejny prosty cykl, który odwiedza wszystkie węzły o niższej masie całkowitejwtedy i tylko wtedy, gdy nie stosuje się krawędzi ciężaru która odpowiada przypisaniu ; lub równoważnie wtedy i tylko wtedy, gdy istnieje inne zadowalające przypisanieφ t = t r u e | V | + 1 t = t r u e T | V | 2 t = t r u e φ t = f a l s e φT.φt=trumi|V.|+1t=trumiT.|V.|2)t=trumiφw którym ; ale może to być prawdą tylko wtedy, gdy oryginalna formuła jest zadowalająca.t=fazalsmiφ

Zastanowię się więcej i napiszę formalny dowód (jeśli nie okaże się, że jest źle :-). Daj mi znać, jeśli potrzebujesz dodatkowych informacji na temat jednego lub więcej powyższych fragmentów.

wprowadź opis zdjęcia tutaj

Jak zauważył domotorp, interesującą konsekwencją jest to, że następujący problem jest NP-zupełny: Czy biorąc pod uwagę wykres i ścieżkę hamiltonowską, ma cykl hamiltonowski?Gsolsol

Marzio De Biasi
źródło
4
Więc zasadniczo pokazujesz, że biorąc pod uwagę wykres i ścieżkę H, to NPc decyduje, czy ma cykl H, prawda?
domotorp
Wygląda świetnie. Dzięki za włożenie wysiłku w napisanie. Kilka zmian, aby bezpośrednio odpowiedzieć na moje pytanie: Krawędzie wykresu powinny mieć wagę 1, z wyjątkiem tej specjalnej krawędzi, która powinna być ważona 2, a nie-krawędzie powinny być ważone 3.
Lance Fortnow
1
Jeśli usuniesz tę określoną krawędź z , wtedy H 1 stanie się ścieżką H, a H 2 pozostanie cyklem H, więc zasadniczo pokazujesz to, co napisałem, prawda? Dla mnie to stwierdzenie wygląda bardziej interesująco niż pierwotne pytanie. GH1H2
domotorp
@domotorp: masz rację! :)
Marzio De Biasi
2
arxiv.org/pdf/1403.3431.pdf autor: Marzio De Biasi
T ....
5

Papadimitriou i Steiglitz (1977) wykazali zupełność NP tego problemu.

Marcus Ritt
źródło
Ojej ... Mam wrażenie, jakbyś „przywitał kierownicę” :-) Papier jest za paywallem SIAM, czy dowód jest podobny do mojego?
Marzio De Biasi,
Nie mam dostępu do gazety, ale możesz znaleźć dowody także w części 19.9 ich książki , która może być bardziej dostępna.
Marcus Ritt,
Ok dzięki! Dowód jest inny (modyfikują instancję problemu obwodu hamiltonowskiego do G ′, która zawsze ma ścieżkę hamiltonowską, ale ma obwód hamiltonowski tylko wtedy, gdy G ma obwód hamiltonowski). Ale muszę zaktualizować artykuł, który opublikowałem w arXiv i przyjąć do wiadomości, że nie jest to nowy wynik (lub go usunąć). Co myślisz? solsolsol
Marzio De Biasi,
@Marzio de Biasi Myślę, że aktualizacja dokumentu jest w porządku. Twój alternatywny dowód jest nadal interesujący.
Marcus Ritt