11.25

Membership in NP.
Given a sequence of vertices
  [math]P=(v_{1},v_{2},\dots ,v_{m})[/math],
we can check in O([math]m^{2}[/math]) time that
1. every pair [math](v_{i},v_{i+1})[/math] is an edge of [math]G[/math],
2. all vertices appearing in P are distinct, and
3. [math]m\ge k[/math].
Thus a nondeterministic algorithm can “guess” such a path and verify it in polynomial time, so Longest Path is in NP.

NP-hardness.
We reduce the known NP-complete problem Hamiltonian Path (HP) to Longest Path (LP).
HP instance: graph [math]G=(V,E)[/math] with [math]n=|V|[/math].
Transformation (performed in time O([math]n+|E|[/math])):
    output the pair [math](G,k)[/math] where [math]k=n[/math].
Correctness: • If G has a Hamiltonian path, that path visits all n vertices, so the LP-instance admits a path of length at least k. • Conversely, a path of length ≥n can visit at most n distinct vertices, hence exactly n and therefore visits every vertex once; this is a Hamiltonian path in G.
Thus [math]G\in\text{HP}\iff(G,n)\in\text{LP}[/math]. Because the reduction is polynomial, LP is NP-hard.

Conclusion.
Longest Path is both in NP and NP-hard, so it is NP-complete.

Verifier pseudocode.
verify(G, k, P):
  if |P| < k: reject
  for i = 1 … |P|-1:
    if (P[i], P[i+1]) ∉ E(G): reject
  if P contains a repeated vertex: reject
  accept

Back to Chapter 11