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?