← Reductions

HAMPATH ≤p HAMCYCLE

A polynomial-time mapping reduction showing that if HAMCYCLE is decidable in polynomial time, so is HAMPATH. Combined with the reverse direction, this is part of how both problems are known to be NP-complete.

The two problems

HAMPATH
Instance: An undirected graph G and two vertices s, t.
Question: Does G contain a Hamiltonian path from s to t (a path visiting every vertex exactly once)?
HAMCYCLE
Instance: An undirected graph G′.
Question: Does G′ contain a Hamiltonian cycle (a cycle visiting every vertex exactly once)?

The construction

Given a HAMPATH instance ⟨G, s, t⟩, build a HAMCYCLE instance G′ as follows:

  1. Take all vertices and edges of G.
  2. Add one fresh vertex u (not in G).
  3. Add exactly two edges: u–s and u–t.

The construction adds one vertex and two edges, so it runs in O(|V| + |E|) time — polynomial in the size of G.

Visualization

Step 1 / 4HAMPATH instance
sv₁v₂t

Input ⟨G, s, t⟩. The thick edges form a Hamiltonian path from s to t. Dashed edges are other edges of G that the path does not use.

Correctness

(⇒) If G has a Hamiltonian path s → … → t, then in G′ we can extend it through the new vertex: s → … → t → u → s. This visits every vertex of G exactly once, plus u once, and closes back to s — a Hamiltonian cycle in G′.
(⇐) If G′ has a Hamiltonian cycle, then u must appear in it. The only neighbors of u in G′ are s and t, so the cycle uses edges u–s and u–t. Deleting u from the cycle leaves a path between s and t that visits every other vertex exactly once — a Hamiltonian path from s to t in G.
Hence ⟨G, s, t⟩ ∈ HAMPATH iff G′ ∈ HAMCYCLE, and the map ⟨G, s, t⟩ ↦ G′ is computable in polynomial time. ∎