Czy najdłuższy problem szlaku jest łatwiejszy niż problem najdłuższej ścieżki?

Najdłuższy problem ze ścieżką to trudność NP. (Typowy?) Dowód polega na zmniejszeniu problemu ścieżki hamiltonowskiej (która jest NP-zupełna). Zauważ, że tutaj ścieżka jest uważana za (węzłową) prostą. Oznacza to, że żaden wierzchołek nie może wystąpić więcej niż jeden raz na ścieżce. Oczywiście jest to również proste dla krawędzi (żadna krawędź nie pojawi się więcej niż raz na ścieżce).

A co jeśli odrzucimy wymóg znalezienia prostej ścieżki (węzła) i trzymamy się znalezienia prostej ścieżki (szlaku). Na pierwszy rzut oka, ponieważ znalezienie szlaku Eulera jest znacznie łatwiejsze niż znalezienie ścieżki hamiltonowskiej, można mieć nadzieję, że znalezienie najdłuższego szlaku byłoby łatwiejsze niż znalezienie najdłuższej ścieżki. Nie mogę jednak znaleźć żadnego odniesienia, które by to potwierdzało, a tym bardziej takiego, który zapewnia algorytm.

Zauważ, że jestem świadomy argumentu przedstawionego tutaj: /programming/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph Jednak argument wydaje się wadliwy w swojej obecnej formie, ponieważ w zasadzie pokazuje, że można rozwiązać prosty przypadek krawędzi, rozwiązując prosty przypadek węzła na innym wykresie (więc redukcja jest niewłaściwa). Nie jest jasne, czy redukcję można łatwo zmienić, aby działała również w drugą stronę. (Mimo to pokazuje, że problem z najdłuższymi szlakami nie jest trudniejszy niż problem z najdłuższymi ścieżkami.)

Czy są więc znane wyniki wyszukiwania najdłuższych szlaków (ścieżki proste)? Złożoność (klasa)? (Wydajny) algorytm?

graph-theory graph-algorithms hamiltonian-paths Jaspis
źródło

To nie jest dokładnie ten sam problem, ale spójrz na problem Minimalnego rozszerzenia euilerian, który jest dość podobny.

Być może nie zrozumiałem dobrze pytania, ale ścieżka Hamiltona jest kompletna NP nawet na grafach sześciennych, ponieważ każde przejście węzła wymaga dwóch krawędzi, nie ma możliwości ponownego użycia węzła dwukrotnie, nawet jeśli złagodzimy warunek z prostego węzła ścieżki do prostych krawędzi; więc problem ścieżki hamiltonowskiej pozostaje NP-kompletny.

Marzio De Biasi

@ Bangye: ok, ale na grafach sześciennych, jeśli węzeł zostanie przemierzony jeden raz, wówczas należy użyć 2 krawędzi ... a węzła nie można ponownie przemierzyć (ponieważ jest tylko jedna krawędź nienawrócona). Tak więc w grafach sześciennych węzłów nie można „powtórzyć” (z wyjątkiem ostatniej krawędzi szlaku, która może być incydentem z już przejechanym węzłem)

Marzio De Biasi

Oto odniesienie: AA Bertossi, Problem krawędzi ścieżki hamiltonowskiej jest NP-zupełny, Information Processing Letters, 13 (1981) 157-159.

Lamine

@Lamine: Dzięki za wyjaśnienie. Nie sądzę, że musisz usunąć swoje komentarze, ponieważ byłoby bardzo naturalne, aby najpierw wymyślić podobny pomysł, a zobaczenie, że nie działa, jest naprawdę pomocne.

Yota Otachi

Z powyższych komentarzy: problem cyklu Hamiltona pozostaje NP-kompletny nawet na wykresach siatki o maksymalnym stopniu 3 [1], ale na tych wykresach każde przejście węzła wymaga dwóch krawędzi, a co najwyżej jedna krawędź pozostaje nieużywana, więc węzeł nie może być przemierzany dwukrotnie ścieżką Eulera.

$G = (V,E)$ $|V|$

$u$ $V' = V \cup \{u',u''\}$ $E = E \cup \{(u,u'), (u,u'')\}$ $|V'| = |V|+2$ $u',u''$

[1] Christos H Papadimitriou, Umesh V Vazirani, O dwóch problemach geometrycznych związanych z problemem podróżnego sprzedawcy, Journal of Algorytmy, tom 5, wydanie 2, czerwiec 1984, strony 231-246, ISSN 0196-6774

Marzio De Biasi
źródło

| E |

$|E|$

| V |

$|V|$

| E |

$|E|$

O (1)

$O(1)$

| V |

$|V|$

u^{'}, u^{″}

$u',u''$

Marzio De Biasi

Czy najdłuższy problem szlaku jest łatwiejszy niż problem najdłuższej ścieżki?

Odpowiedzi: