NP-Vollständigkeit vom längsten Pfad beweisen

Question

Aufgabe:

NP-Vollständigkeit des längsten Pfades beweisen

Problem/Ansatz:

Hallo, ich wollte nur mal nachfragen, ob jemand so nett wäre und über den Beweis schauen könnte, ob dieser denn so richtig ist:

Wir nehmen an das Hamilton-Pfad NP schwer ist.

Hamilton-Pfad: Eingabe: Ein ungerichteter Graph G Ausgabe: Enthält G einen Graph der alle Knoten genau einmal besucht ?

Längster Pfad: Eingabe: ein ungerichteter Graph G und k ∈ ℕ. Ausgabe: Enthält G einen Pfad der (mind.) k Knoten genau einmal besucht ?

Zum Beweis:

1) Längster Pfad liegt in NP:

Betrachte den folgenden Algorithmus:
Starte von einem beliebigen Knoten v in G.
Betrachte alle möglichen Pfade von v aus bei denen die Anzahl der besuchten Knoten größer oder gleich k ist.
Sollte es einen Pfad geben, bei dem jeder Knoten nur ein mal besucht wurde, so gib ja zurück, andernfalls nein.

Dieser Algorithmus ist nicht-deterministisch und liegt somit in NP.

2) Längster Pfad ist NP-schwer:

Reduktion des Hamilton-Pfades:

Sei G = (V,E) und k ∈ ℕ beliebig. Ist k > |V| so füge k - |V| viele Knoten zum Graphen an einem beliebigen vorhandenem Knoten in G hinzu. Ist k < |V|, so entferne |V| - k viele Knoten von G aus. Wir erhalten also einen Graph G' = (V',E') mit |V'| = k.

Beachte das die Konstruktion von G' ist polynomieller Zeit verläuft da k - |V| und |V| - k endlich sind.

Dann gibt es in G' genau dann einen Hamilton-Pfad wenn alle Knoten in G' genau einmal besucht wurden. D.h insbesondere das gilt: Es gibt einen längsten Pfad genau dann wenn es einen Hamilton-Pfad gibt.

Also ist längster Pfad NP-schwer.

Answer 1

Dieser Algorithmus ist nicht-deterministisch und liegt somit in NP.

Die Schlussfolgerung ist nicht korrekt. Nicht-Determinismus reicht nicht für NP. Damit eine Problem in NP liegt, muss es eine nicht-deterministische Turingmaschine geben, die das Problem in polynomieller Laufzeit entscheidet.

Mir ist auch nicht ganz klar, wie der Nicht-Determinismus da ins Spiel kommt.

Reduktion des Hamilton-Pfades:

Um Hamilton-Pfad((V,E)) zu lösen genügt es, Längster-Pfad((V,E), |V|) zu lösen.

Sei G = (V,E) und k ∈ ℕ beliebig.

Das Problem Hamilton-Pfad, das du mittels Längster-Pfad lösen möchtest, hat überhaupt kein k als Eingabe.

Also ist längster Pfad NP-schwer.

Eigentlich wolltest du doch NP-Vollständigkeit zeigen, oder? Für NP-Schwere hättest du dir Teil 1 sparen können.