Problem najdłuższej ścieżki

W teorii grafów i informatyce teoretycznej problem najdłuższej ścieżki to problem znalezienia prostej ścieżki o maksymalnej długości w danym grafie . Ścieżkę nazywamy prostą , jeśli nie ma żadnych powtarzających się wierzchołków ; długość ścieżki można mierzyć liczbą jej krawędzi lub (w grafach ważonych ) sumą wag jej krawędzi. W przeciwieństwie do problemu najkrótszej ścieżki , który można rozwiązać w czasie wielomianowym na grafach bez cykli o ujemnej wadze problem z najdłuższą ścieżką jest NP-trudny , a wersja decyzyjna problemu, która pyta, czy istnieje ścieżka o co najmniej określonej długości, jest NP-zupełna . Oznacza to, że problemu decyzyjnego nie można rozwiązać w czasie wielomianowym dla dowolnych grafów, chyba że P = NP . Znane są również wyniki o większej twardości, co pokazuje, że jest to trudne do przybliżenia . Ma jednak liniowe rozwiązanie czasowe dla skierowanych grafów acyklicznych , które ma ważne zastosowania w znajdowaniu ścieżki krytycznej w problemach z harmonogramem.

NP-twardość

NP-twardość nieważonego problemu z najdłuższą ścieżką można pokazać za pomocą redukcji z problemu ścieżki Hamiltona : wykres G ma ścieżkę Hamiltona wtedy i tylko wtedy, gdy jego najdłuższa ścieżka ma długość n - 1, gdzie n jest liczbą wierzchołków w G. _ Ponieważ problem ścieżki Hamiltona jest NP-zupełny, ta redukcja pokazuje, że wersja decyzyjna problemu najdłuższej ścieżki jest również NP-zupełna. W tym problemie decyzyjnym dane wejściowe to wykres G i liczba k ; żądane wyjście to tak jeśli G zawiera ścieżkę o k lub więcej krawędziach i nie w przeciwnym razie.

Gdyby problem najdłuższej ścieżki można było rozwiązać w czasie wielomianowym, można by go użyć do rozwiązania tego problemu decyzyjnego, znajdując najdłuższą ścieżkę, a następnie porównując jej długość z liczbą k . Dlatego problem najdłuższej ścieżki jest NP-trudny. Pytanie „czy w danym grafie istnieje prosta ścieżka o co najmniej k krawędziach” jest NP-zupełne.

W ważonych pełnych grafach z nieujemnymi wagami krawędzi ważony problem najdłuższej ścieżki jest taki sam jak problem ścieżki komiwojażera , ponieważ najdłuższa ścieżka zawsze zawiera wszystkie wierzchołki.

Grafy acykliczne

Najdłuższa ścieżka między dwoma zadanymi wierzchołkami s i t w grafie ważonym G jest tym samym, co najkrótsza ścieżka w grafie − G wyprowadzona z G przez zamianę każdej wagi na jej negację. Dlatego jeśli najkrótsze ścieżki można znaleźć w − G , to najdłuższe ścieżki można również znaleźć w G .

W przypadku większości grafów ta transformacja nie jest użyteczna, ponieważ tworzy cykle o ujemnej długości w − G . Ale jeśli G jest skierowanym grafem acyklicznym (DAG), to nie można utworzyć żadnych ujemnych cykli, a najdłuższą ścieżkę w G można znaleźć w czasie liniowym , stosując algorytm czasu liniowego dla najkrótszych ścieżek w - G , który jest również skierowany wykres acykliczny. W przypadku DAG najdłuższą ścieżkę od wierzchołka źródłowego do wszystkich innych wierzchołków można uzyskać, uruchamiając algorytm najkrótszej ścieżki na − G .

Podobnie dla każdego wierzchołka v w danym DAG długość najdłuższej ścieżki kończącej się na v można uzyskać, wykonując następujące kroki:

Znajdź uporządkowanie topologiczne danego DAG.
Dla każdego wierzchołka v DAG, w porządku topologicznym, oblicz długość najdłuższej ścieżki kończącej się na v , patrząc na jego przychodzących sąsiadów i dodając jeden do maksymalnej długości zarejestrowanej dla tych sąsiadów. Jeśli v nie ma przychodzących sąsiadów, ustaw długość najdłuższej ścieżki kończącej się na v na zero. W obu przypadkach zapisz tę liczbę, aby późniejsze etapy algorytmu miały do niej dostęp.

Po wykonaniu tej czynności najdłuższą ścieżkę w całym DAG można uzyskać, zaczynając od wierzchołka v z największą zarejestrowaną wartością, a następnie wielokrotnie cofając się do przychodzącego sąsiada z największą zarejestrowaną wartością i odwracając kolejność wierzchołków znalezionych w tą drogą.

Jest to równoważne uruchomieniu algorytmu najkrótszej ścieżki na − G .

Ścieżki krytyczne

Metoda ścieżki krytycznej służąca do planowania zestawu działań polega na konstruowaniu ukierunkowanego grafu acyklicznego, w którym wierzchołki reprezentują kamienie milowe projektu, a krawędzie czynności, które należy wykonać po jednym kamieniu milowym i przed kolejnym; każda krawędź jest ważona przez oszacowanie czasu potrzebnego na ukończenie odpowiedniej czynności. Na takim wykresie najdłuższą ścieżką od pierwszego do ostatniego kamienia milowego jest ścieżka krytyczna, która opisuje całkowity czas realizacji projektu.

Najdłuższe ścieżki skierowanych grafów acyklicznych można również zastosować do rysowania grafów warstwowych : przypisanie każdego wierzchołka v skierowanego grafu acyklicznego G do warstwy, której numer jest długością najdłuższej ścieżki kończącej się na v , powoduje przypisanie warstwy dla G z minimum możliwa ilość warstw.

Przybliżenie

Björklund, Husfeldt i Khanna (2004) piszą, że problem z najdłuższą ścieżką w nieważonych grafach nieskierowanych „słynie z trudności w zrozumieniu jego twardości w przybliżeniu”. Najlepszy algorytm aproksymacji czasu wielomianowego znany w tym przypadku osiąga tylko bardzo słaby współczynnik aproksymacji, ${\ Displaystyle n/\ exp (\ Omega ({\ sqrt {\ log n}} ))}$ . dla wszystkich ${\ Displaystyle \ epsilon > 0}$ , nie jest możliwe przybliżenie najdłuższej ścieżki z dokładnością do ${\ Displaystyle 2 ^ {(\ log n) ^ {1- \ epsilon}}},$ chyba że NP jest zawarte w quasi- wielomianowy czas deterministyczny ; istnieje jednak duża luka między tym wynikiem nieprzybliżenia a znanymi algorytmami aproksymacji dla tego problemu.

W przypadku grafów nieważonych, ale skierowanych, znane są wyniki silnej nieaproksymacji. Dla każdego $Displaystyle$ można przybliżyć do współczynnika $n ^ {1-\ epsilon}},$ chyba że P = NP i przy silniejszych założeniach teorii złożoności nie można go przybliżyć do współczynnika ${\ Displaystyle n/\ log ^ {2+ \ epsilon} n}$ . Kodowanie kolorami technika może być użyta do znalezienia ścieżek o długości logarytmicznej, jeśli istnieją, ale daje to współczynnik przybliżenia tylko $}$ )

Złożoność parametryczna

Problem z najdłuższą ścieżką jest możliwy do rozwiązania ze stałymi parametrami , gdy jest sparametryzowany przez długość ścieżki. Na przykład można go rozwiązać w czasie liniowym w rozmiarze wykresu wejściowego (ale wykładniczym w długości ścieżki) za pomocą algorytmu, który wykonuje następujące kroki:

Wykonaj przeszukiwanie grafu w głąb . Niech $będzie$ głębokością wynikowego drzewa w pierwszej kolejności .
Użyj sekwencji ścieżek od korzenia do liści drzewa wyszukiwania w głąb, w kolejności, w jakiej zostały przeszukane przez przeszukiwanie, aby skonstruować rozkład ścieżki wykresu o szerokości ścieżki re { \ displaystyle $}$ .
Zastosuj programowanie dynamiczne do tego $Displaystyle$ ścieżki, aby znaleźć najdłuższą ścieżkę w czasie , gdzie jest liczbą wierzchołków $O (d! 2 ^ {d} n)}$ na wykresie.

Ponieważ ścieżka wyjściowa ma długość co najmniej tak dużą jak $\$ czas działania jest również ograniczony przez $! 2 ^ {\ ell} n)}$ , gdzie $.$ długością najdłuższej ścieżki Za pomocą kodowania kolorami zależność od długości ścieżki można zredukować do jednowykładniczej. Podobna technika programowania dynamicznego pokazuje, że problem z najdłuższą ścieżką jest również wykonalny ze stałymi parametrami, gdy jest sparametryzowany przez szerokość drzewa wykresu.

W przypadku wykresów o ograniczonej szerokości kliki najdłuższą ścieżkę można również rozwiązać za pomocą algorytmu programowania dynamicznego w czasie wielomianowym. Jednak wykładnik wielomianu zależy od szerokości kliki wykresu, więc ten algorytm nie jest możliwy do zastosowania ze stałymi parametrami. $.$ najdłuższą ścieżką, sparametryzowany przez szerokość kliki, jest trudny dla złożoności , co pokazuje, że jest mało prawdopodobne, aby o stałych parametrach istniał

Specjalne klasy grafów

Algorytm w czasie liniowym do znajdowania najdłuższej ścieżki w drzewie został zaproponowany przez Dijkstrę w latach 60-tych, natomiast formalny dowód tego algorytmu został opublikowany w 2002 roku. Co więcej, najdłuższą ścieżkę można obliczyć w czasie wielomianowym na drzewach ważonych, na grafach blokowych , na kaktusach , na dwudzielnych grafach permutacyjnych i na grafach Ptolemeusza .

Dla klasy grafów interwałowych znany jest algorytm czasowy $. To podejście do$ podejście do programowania dynamicznego zostało wykorzystane do uzyskania algorytmów czasu wielomianowego na większych klasach grafów kołowo-łukowych i grafów współporównywalności (tj . ${\ Displaystyle O (n ^ {4})}$ . Ten ostatni algorytm jest oparty na specjalnych właściwościach uporządkowania wierzchołków grafów współporównywalności w leksykograficznym przeszukiwaniu głębi (LDFS). W przypadku wykresów współporównywalności znany jest również alternatywny algorytm czasu wielomianowego o wyższym czasie działania, który jest oparty na diagramie Hassego częściowo uporządkowanego zbioru zdefiniowanego przez ${\ Displaystyle O (n ^ {7})}$ dopełnienie grafu współporównywalności danych wejściowych.

Co więcej, problem najdłuższej ścieżki można rozwiązać w czasie wielomianowym na dowolnej klasie grafów o ograniczonej szerokości drzewa lub ograniczonej szerokości kliki, takich jak grafy dziedziczne odległości . Wreszcie, jest to wyraźnie NP-trudne dla wszystkich klas grafów, w których problem ścieżki Hamiltona jest NP-trudny, na przykład na grafach podzielonych , grafach kołowych i grafach planarnych .

Prostym modelem skierowanego grafu acyklicznego jest model Price , opracowany przez Dereka J. de Solla Price'a do reprezentowania sieci cytowań . Jest to wystarczająco proste, aby umożliwić znalezienie wyników analitycznych dla niektórych właściwości. Na przykład długość najdłuższej ścieżki, od n-tego węzła dodanego do sieci do pierwszego węzła w sieci, skaluje się jako ${\ Displaystyle \ ln (n)}$ .