← Reductions

HAMCYCLE ≤p HAMPATH

The reverse direction of the HAMPATH/HAMCYCLE pair. Together with HAMPATH ≤p HAMCYCLE, this shows that the two problems are polynomial-time equivalent.

The two problems

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

The construction

Given a HAMCYCLE instance G, pick any vertex v ∈ G and build a HAMPATH instance ⟨G′, s, t⟩ as follows:

  1. Take all vertices and edges of G.
  2. Add a fresh vertex v′ whose neighborhood matches v: for every neighbor u of v in G, add edge u–v′ in G′.
  3. Add two more fresh vertices s and t.
  4. Add edges s–v and v′–t. (s is incident only to v; t is incident only to v′.)

The construction adds three vertices and at most deg(v) + 2 edges — polynomial in the size of G.

Visualization

Step 1 / 4HAMCYCLE instance
vabc

Input: graph G. The thick edges form a Hamiltonian cycle v → a → b → c → v. Pick any vertex of G — here we pick v.

Correctness

(⇒) If G has a Hamiltonian cyclev → u₁ → u₂ → … → uₙ → v, then in G′ the corresponding path is s → v → u₁ → u₂ → … → uₙ → v′ → t. The closing edge uₙ–v of the cycle becomes uₙ–v′ in G′ (which exists because v′ inherited v's neighborhood). This visits every vertex of G plus v′, s, t exactly once.
(⇐) If G′ has a Hamiltonian path from s to t,then s must be followed by v (s's only neighbor) and t must be preceded by v′ (t's only neighbor). Stripping s and t leaves a path v → … → v′ in G′. Identifying v′ with v (they have the same neighborhood in G), the path becomes a Hamiltonian cycle through v in G.
Hence G ∈ HAMCYCLE iff ⟨G′, s, t⟩ ∈ HAMPATH, and the map is computable in polynomial time. ∎