Source: VERTEX COVER (MinimumVertexCover)
Target: HAMILTONIAN PATH (HamiltonianPath)

Motivation: Establishes NP-completeness of HAMILTONIAN PATH by composing the VC→HC reduction (Theorem 3.4) with a simple HC→HP modification. This two-step approach shows the path variant is NP-complete without requiring a fundamentally new gadget construction. The reduction is described in Section 3.1.4 of Garey & Johnson.

Reference: Garey & Johnson, Computers and Intractability, Section 3.1.4, p. 60; A1.3 GT39

GJ Source Entry

GT39 HAMILTONIAN PATH
INSTANCE: Graph G = (V,E).
QUESTION: Does G contain a Hamiltonian path, that is, a path that visits each vertex in V exactly once?
Reference: Chapter 3, [Garey and Johnson, 1979]. Transformation from VERTEX COVER.

Reduction Algorithm

Summary:
Given a MinimumVertexCover instance (G = (V, E), K), construct a HamiltonianPath instance G'' as follows:

1. First stage (VC → HC): Apply the Theorem 3.4 construction to produce a HamiltonianCircuit instance G' = (V', E') with K selector vertices a₁, ..., a_K, cover-testing gadgets (12 vertices per edge), vertex path edges, and selector connection edges. See R279 for details.

2. Second stage (HC → HP): Modify G' to produce G'':

   • Add three new vertices: a₀, a_{K+1}, and a_{K+2}.
   • Add two pendant edges: {a₀, a₁} and {a_{K+1}, a_{K+2}}.
   • For each vertex v ∈ V, replace the edge {a₁, (v, e_{v[deg(v)]}, 6)} with {a_{K+1}, (v, e_{v[deg(v)]}, 6)}.

3. Correctness: a₀ and a_{K+2} have degree 1, so any Hamiltonian path must start/end at these vertices. The path runs a₀ → a₁ → [circuit body] → a_{K+1} → a_{K+2}. A Hamiltonian path exists in G'' iff a Hamiltonian circuit exists in G' iff G has a vertex cover of size ≤ K.

Vertex count: 12m + K + 3
Edge count: 16m − n + 2Kn + 2

Size Overhead

Symbols:

• n = num_vertices of source MinimumVertexCover instance (|V|)
• m = num_edges of source MinimumVertexCover instance (|E|)
• K = cover size bound

Derivation:

• Vertices: 12m (gadgets) + K (selectors) + 3 (new vertices a₀, a_{K+1}, a_{K+2}) = 12m + K + 3
• Edges: from VC→HC we get 16m − n + 2Kn; the HC→HP step replaces n edges and adds 2, net +2: total = 16m − n + 2Kn + 2

Validation Method

• Closed-loop test: construct a small MinimumVertexCover instance, reduce to HamiltonianPath, solve with BruteForce, verify a Hamiltonian path exists iff the graph has a vertex cover of size ≤ K.
• Verify that any Hamiltonian path found starts and ends at the degree-1 vertices a₀ and a_{K+2}.
• Test with a triangle (K₃, K=2): should have Hamiltonian path. With K=1: should not.
• Verify vertex and edge counts match formulas.

Example

Source instance (MinimumVertexCover):
Graph G with 3 vertices {0, 1, 2} forming a path P₃:

• Edges: e₀={0,1}, e₁={1,2}
• n = 3, m = 2, K = 1
• Minimum vertex cover: {1} (covers both edges)

Constructed target instance (HamiltonianPath):

• Stage 1 (VC→HC): 12×2 + 1 = 25 vertices, 16×2 − 3 + 2×1×3 = 35 edges
• Stage 2 (HC→HP): +3 vertices, +2 edges → 28 vertices, 37 edges

Solution mapping:

• Vertex cover {1} with K=1 → Hamiltonian circuit in G' with selector a₁ routing through vertex 1's gadgets
• Modified to Hamiltonian path in G'': a₀ → a₁ → [traverse gadgets for vertex 1, covering both edge gadgets] → a₂ → a₃
• All 28 vertices visited exactly once ✓

References

• Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Problem GT39, Section 3.1.4.