In der Graphentheorie und Theoretische Informatik, ist der längste Weg Problem das Problem der Suche nach einem einfachen Weg der maximalen Länge in einem gegebenen Graphen. Ein Pfad heißt einfach, wenn sie keine wiederholten Ecken haben; die Länge eines Pfads kann entweder durch die Anzahl seiner Kanten gemessen werden, oder durch die Summe der Gewichte der Kanten. Im Gegensatz zu dem kürzesten Weg Problem, das in Polynomzeit in Graphen ohne negative Gewichtszyklen gelöst werden kann, ist der längste Pfad Problem NP-hart, was bedeutet, dass sie nicht in Polynomzeit für beliebige Graphen sofern P = NP gelöst werden. Stärker Härteergebnisse sind ebenfalls bekannt, die zeigen, dass es schwierig ist, anzunähern. Allerdings hat es eine lineare Zeitlösung für eine gerichtete azyklische Graphen, die wichtige Anwendungen bei der Suche nach den kritischen Pfad in Planungsprobleme hat.

NP-Härte

Der NP-Härte des ungewichteten längsten Problem lässt sich mit einer Verringerung von der Hamilton-Pfad Problem darstellen: einen Graphen G einen Hamilton-Pfad dann und nur dann, wenn die längste Pfad Länge n - 1, wobei n die Anzahl der Ecken in G . Da der Hamilton-Pfad Problem NP-vollständig ist, diese Reduktion zeigt, dass die Entscheidungsversion des längsten Pfades Problem ist auch NP-vollständig. In diesem Entscheidungsproblem ist die Eingabe ein Graph G und eine Anzahl k; der gewünschte Ausgang "ja" ist, wenn G einen Pfad der k oder mehr Kanten, keine anders.

Wenn der längsten Pfad Problem könnte in polynomieller Zeit gelöst werden kann, kann es verwendet werden, um diese Entscheidung Problem zu lösen, indem sie eine längsten Pfad und dann den Vergleich seiner Länge auf die Anzahl k werden. Daher ist der längste Weg Problem NP-schwer. Es ist nicht NP-vollständig ist, weil es nicht eine Entscheidung Problem.

In gewichtete vollständige Graphen mit nicht-negativen Kantengewichten, ist die gewichtete längsten Pfad Problem das gleiche wie das Travelling Salesman-Wege-Problem, weil der längsten Pfad umfasst immer alle Ecken.

Azyklische Graphen und kritische Pfade

A längsten Pfad zwischen zwei gegebenen Knoten s und t in einem gewichteten Graphen G ist die gleiche wie ein kürzester Pfad in einem Graphen G aus G durch Verändern jedes Gewicht auf seine Negation abgeleitet. Wenn daher kürzesten Pfade kann -G gefunden wurde, dann längsten Wege können auch in G gibt

Für die meisten Grafiken, ist diese Umwandlung nicht sinnvoll, weil es Kreise negativer Länge in G erstellt. Aber wenn G einen gerichteten azyklischen Graphen, werden keine negativen Zyklen erzeugt werden, und am längsten Pfade in G kann in linearer Zeit durch Anlegen eines linearen Algorithmus für kürzeste Wege in -G, die auch ein gerichteter azyklischer Graph gefunden werden. Zum Beispiel für jeden Scheitelpunkt v in einer gegebenen DAG, wobei die Länge des längsten Pfades endend bei V kann durch die folgenden Schritte erhalten werden:

• Finden Sie einen topologischen Anordnung der gegebenen DAG.
• Für jeden Knoten v der DAG, in der topologischen Anordnung, berechnen Sie die Länge der längsten Pfad endet an v indem seine eingehenden Nachbarn und Zugabe von einem auf die maximale Länge für die Nachbarn aufgezeichnet. Wenn v keine eingehenden Nachbarn, stellen Sie die Länge des längsten Weg endet bei V auf Null. In beiden Fällen erfassen Sie diese Nummer, so dass spätere Schritte des Algorithmus darauf zugreifen können.

Sobald dies geschehen ist, kann der längste Pfad in dem gesamten DAG, indem man bei dem Knoten v mit der größten aufgezeichneten Wert, dann wiederholt Schritt zurück bis in die ankommende Nachbar mit der größten aufgezeichneten Wert und Umkehren der Reihenfolge der Eckpunkte im Ergebnis erhalten werden, diesen Weg.

Der kritische Pfad-Methode für die Planung eine Reihe von Aktivitäten umfasst den Bau eines gerichteten azyklischen Graphen, in dem die Eckpunkte repräsentieren Projektmeilensteine ​​und die Kanten repräsentieren Aktivitäten, die nach ein Meilenstein und bevor ein anderer durchgeführt werden müssen; jede Kante wird durch eine Schätzung der Höhe der Zeit, die entsprechende Tätigkeit wird dauern gewichtet. In einem solchen Diagramm ist die längsten Pfad vom ersten Meilenstein auf die letzte der kritische Pfad, der die Gesamtzeit für die Durchführung des Projekts beschreibt.

Längsten Wege des azyklischen Graphen kann auch in Ebenen unterteilten Graphen Zeichnung angewendet werden: Zuweisen jedes Vertex v eines gerichteten azyklischen Graphen G auf die Schicht, deren Anzahl die Länge des längsten Pfades endend bei V ergibt eine Schichtzuweisung für G mit einem Minimum mögliche Anzahl der Schichten.

Annäherung

Bjorklund, Husfeldt & amp; Khanna zu schreiben, dass die längsten Pfad Problem in ungewichteten ungerichtete Graphen "ist berüchtigt für die Schwierigkeit, das Verständnis seiner Annäherung Härte". Die beste Polynomzeit Näherungsalgorithmus für diesen Fall bekannt erreicht nur eine sehr schwache Näherung Verhältnis ,. Für alle ist es nicht möglich, den längsten Weg innerhalb eines Faktors von sofern NP innerhalb quasi-Polynom deterZeit versehenen nähern; Jedoch gibt es eine große Lücke zwischen diesem inapproximability Ergebnisses und der bekannten Näherungsalgorithmen für dieses Problem.

Im Falle der ungewichteten aber gerichteten Graphen werden starke inapproximability Ergebnisse bekannt. Für jeden der Fehler nicht innerhalb eines Faktors von sofern P = NP, und mit einer stärkeren Komplexität theoretischen Annahmen er nicht innerhalb eines Faktors von angenähert werden angenähert werden. Die Farbcodierung kann angewandt werden, um Pfade von logarithmischen Länge zu finden, wenn sie vorhanden sind, aber dies ergibt eine Approximation Verhältnis von nur.

Parametrisierte Komplexität

Der längste Pfad Problem behoben Parameter handhabbar, wenn durch die Länge des Wegs parametriert. Zum Beispiel kann es in der Zeit linear in der Größe des Eingangs Graphen gelöst werden, durch einen Algorithmus, der die folgenden Schritte ausführt:

• Führen eine Tiefensuche des Graphen. Sei die Tiefe des resultierenden Tiefensuchbaum.
• Verwenden der Sequenz der Wurzel-zu-Blatt-Pfade des Tiefensuchbaum in der Reihenfolge, in der sie von der Suche durchlaufen wurden, um einen Weg Zersetzung des Diagramms zu konstruieren, mit pathwidth.
• Gelten dynamischen Programmierung zu diesem Pfad Zersetzung zu einer längsten Pfad zu ermitteln, wobei die Anzahl der Knoten in dem Graph.

Da der Ausgangspfad hat eine Länge mindestens so groß wie die Laufzeit ebenfalls begrenzt, wobei die Länge des längsten Pfades. Verwenden von Farbcodierung kann die Abhängigkeit von Weglänge reduziert, um einzeln exponentiellen werden. Eine ähnliche Dynamik Programmiertechnik zeigt, dass die längsten Wege-Problem ist auch fester Parameter gefügig, wenn durch die Baumweite des Graphen parametriert.

Für Graphen beschränkter Clique Breiten kann der längsten Pfad auch durch einen Polynomialzeit dynamischen Programmieralgorithmus gelöst werden. Der Exponent des Polynoms ist jedoch abhängig von der Clique Breite des Graphen, so dass diese Algorithmen nicht fixiert Parameter lenkbar. Die längste Wege-Problem, indem Clique Breiten parametriert, ist schwer für die parametrierte Komplexitätsklasse, die zeigen, dass ein Festparameter gefügig Algorithmus ist unwahrscheinlich, zu existieren.

Spezielle Klassen von Graphen

Die längste Pfad Problem kann in polynomieller Zeit auf die Ergänzung der Vergleichbarkeit Graphen gelöst werden. Es kann auch in polynomieller Zeit für jede Klasse von Graphen mit beschränkter Baumweite oder beschränkter Clique Breiten, wie beispielsweise die Fern erbliche Graphen gelöst werden. Allerdings ist es NP-schwer, auch wenn beschränkt, um Diagramme, Kreisdiagramme oder planaren Graphen aufgeteilt.