[Rule] HamiltonianCircuit to TravelingSalesman

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] HamiltonianCircuit to TravelingSalesman"
labels: rule
assignees: ''
canonical_source_name: 'HamiltonianCircuit'
canonical_target_name: 'TravelingSalesman'
source_in_codebase: true
target_in_codebase: true

Source: HamiltonianCircuit
Target: TravelingSalesman
Motivation: Establishes NP-completeness of TravelingSalesman via one of the most classical and widely-taught polynomial-time reductions in complexity theory. The reduction embeds the graph into a complete weighted graph with distances 1 (for existing edges) and 2 (for non-edges); the optimal TSP tour has weight n if and only if the source graph has a Hamiltonian circuit. This is a textbook example appearing in virtually every algorithms course.

Reference: Garey & Johnson, Computers and Intractability, ND22, p.211

GJ Source Entry

[ND22] TRAVELING SALESMAN
INSTANCE: Set C of m cities, distance d(c_i,c_j)∈Z^+ for each pair of cities c_i,c_j∈C, positive integer B.
QUESTION: Is there a tour of C having length B or less, i.e., a permutation <c_{π(1)},c_{π(2)},...,c_{π(m)}> of C such that
(∑_{i=1}^{m-1} d(c_{π(i)},c_{π(i+1)})) + d(c_{π(m)},c_{π(1)}) ≤ B ?
Reference: Transformation from HAMILTONIAN CIRCUIT.
Comment: Remains NP-complete even if d(c_i,c_j)∈{1,2} for all c_i,c_j∈C. Special cases that can be solved in polynomial time are discussed in [Gilmore and Gomory, 1964], [Garfinkel, 1977], and [Syslo, 1973]. The variant in which we ask for a tour with "mean arrival time" of B or less is also NP-complete [Sahni and Gonzalez, 1976].

Reduction Algorithm

Summary:
Given a HamiltonianCircuit instance G = (V, E) with n = |V| vertices, construct a TravelingSalesman instance as follows:

1. Graph: Construct the complete graph K_n on vertex set V with n(n-1)/2 edges.

2. Edge weights: Assign weights to each edge of K_n:

   • w(u, v) = 1 if {u, v} ∈ E (the edge exists in G)
   • w(u, v) = 2 if {u, v} ∉ E (the edge does not exist in G)

3. Correctness (forward): If G has a Hamiltonian circuit v_1 → v_2 → ... → v_n → v_1, then selecting the corresponding n edges in K_n gives a tour of total weight n × 1 = n, since every consecutive pair {v_i, v_{i+1}} and {v_n, v_1} is an edge in G and thus has weight 1.

4. Correctness (reverse): If the optimal TSP tour has weight n, then since any tour visits all n vertices and uses exactly n edges, each with weight ≥ 1, the minimum possible weight is n. Achieving weight exactly n requires every edge in the tour to have weight 1, meaning every consecutive pair is an edge in G. Therefore, the tour is a Hamiltonian circuit in G.

Key invariant: The optimal TSP tour has weight exactly n if and only if it uses only edges of weight 1, which correspond exactly to the edges of G. Hence the minimum tour weight is n iff G has a Hamiltonian circuit.

Representation note: HamiltonianCircuit uses a vertex permutation representation (config[i] ∈ {0, ..., n-1}), while TravelingSalesman uses binary edge selection (config[e] ∈ {0, 1} for each edge). Solution extraction converts the TSP edge selection back to a vertex permutation: traverse the selected edges to recover the cycle ordering.

Time complexity of reduction: O(n^2) to construct the complete graph and assign weights.

Size Overhead

Symbols:

• n = num_vertices of source HamiltonianCircuit instance (|V|)
• m = num_edges of source HamiltonianCircuit instance (|E|)

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_vertices * (num_vertices - 1) / 2

Derivation: The TSP instance has the same vertex set as the source graph (n vertices). The complete graph K_n has n(n-1)/2 edges.

Validation Method

• Closed-loop test: reduce a small HamiltonianCircuit instance G to TravelingSalesman, solve the TSP with BruteForce, extract the solution, verify that if the optimal tour weight equals n then the extracted edges form a Hamiltonian circuit in G, and vice versa.
• Test with known YES instance: the triangular prism (6 vertices, 9 edges) has a Hamiltonian circuit. The TSP instance should have an optimal tour of weight 6.
• Test with known NO instance: the Petersen graph has no Hamiltonian circuit. The TSP instance should have an optimal tour of weight > 10.
• Verify edge weights: all entries are 1 or 2, and edges in G have weight 1.

Example

Source instance (HamiltonianCircuit):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0}, {0,3}, {1,4}, {2,5}
• (Triangular prism / prism graph)
• Hamiltonian circuit exists: 0 → 1 → 2 → 3 → 4 → 5 → 0

Constructed target instance (TravelingSalesman):

• 6 vertices, 15 edges (complete graph K_6)
• Edge weights:
  • Weight 1 (edges in G): {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {0,5}, {0,3}, {1,4}, {2,5}
  • Weight 2 (non-edges): {0,2}, {0,4}, {1,3}, {1,5}, {2,4}, {3,5}

Solution mapping:

• TSP optimal tour: edges {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {0,5} selected
• Tour weight: 1+1+1+1+1+1 = 6 = n
• All selected edges have weight 1 → all are edges in G → this is a Hamiltonian circuit in G
• Extracted HC solution (vertex permutation): [0, 1, 2, 3, 4, 5]

Alternative tour: edges {0,3}, {3,2}, {2,5}, {5,4}, {4,1}, {1,0} selected

• Tour weight: 1+1+1+1+1+1 = 6 = n
• Also a valid Hamiltonian circuit in G
• Extracted HC solution: [0, 3, 2, 5, 4, 1]

References

• [Gilmore and Gomory, 1964]: [Gilmore1964] P. C. Gilmore and R. E. Gomory (1964). "Sequencing a one state-variable machine: a solvable case of the traveling salesman problem". Operations Research 12, pp. 655–679.
• [Garfinkel, 1977]: [Garfinkel1977] R. S. Garfinkel (1977). "Minimizing wallpaper waste, {Part} 1: a class of traveling salesman problems". Operations Research 25, pp. 741–751.
• [Syslo, 1973]: [Syslo1973] Maciej M. Syslo (1973). "A new solvable case of the traveling salesman problem". Mathematical Programming 4, pp. 347–348.
• [Sahni and Gonzalez, 1976]: [Gonzalez1976] T. Gonzalez and S. Sahni (1976). "Open shop scheduling to minimize finish time". Journal of the Association for Computing Machinery 23, pp. 665–679.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source problem HamiltonianCircuit not in codebase; novel reduction but requires new model first
Non-trivial	✅ Pass	Classic gadget construction: embed graph into complete weighted graph with distance encoding
Correctness	✅ Pass	Garey & Johnson ND22 reference verified; well-known textbook reduction
Well-written	❌ Fail	Overhead table uses num_cities which is not a valid TSP size field; type mismatch between satisfaction and optimization problem

Overall: 1 passed, 1 warning, 1 failed

---

Usefulness

The source problem HamiltonianCircuit does not exist in the codebase (pred show HamiltonianCircuit fails). The issue metadata correctly notes source_in_codebase: false. Since no path exists from any Hamiltonian Circuit problem to TravelingSalesman (the source problem simply does not exist yet), this reduction is novel and would add a new entry point to the reduction graph.

However, implementing this rule requires first implementing the HamiltonianCircuit model. The issue should either be paired with a [Model] issue for HamiltonianCircuit or blocked on one.

Result: Warn — useful reduction, but depends on an unimplemented source model.

Non-trivial

The reduction involves genuine structural transformation:

• Constructs a complete graph K_n from the input graph G
• Assigns edge weights using a distance encoding (1 for existing edges, 2 for non-edges)
• Sets a bound B = n that discriminates Hamiltonian circuits from non-Hamiltonian tours

This is a classic NP-completeness reduction with a non-trivial distance gadget. Pass.

Correctness

Reference verification:

• Garey & Johnson, ND22 (p.211): This is the canonical reference. The book is well-known and the TSP entry (ND22) is confirmed in the references knowledge base (GJ# GT46 for TSP, GT34 for Hamiltonian Circuit). The reduction from Hamiltonian Circuit is explicitly stated in the GJ entry.
• The reduction algorithm (distances 1/2, bound B=n) matches the standard textbook presentation confirmed by multiple university course materials (OpenDSA, UMD CMSC 451, CMU, ProofWiki).
• The correctness argument (forward and reverse directions) is sound: a tour of length exactly n requires all edges to have distance 1, which means all edges are in G, forming a Hamiltonian circuit.
• The comment about d(c_i,c_j) in {1,2} remaining NP-complete is directly from GJ.

Supplementary references in the issue: The references to Gilmore & Gomory (1964), Garfinkel (1977), Syslo (1973), and Sahni & Gonzalez (1976) are copied from the GJ entry. Note: the Sahni & Gonzalez citation lists "Gonzalez and Sahni (1976)" about open shop scheduling, which is a different paper — the actual reference for TSP mean arrival time variant should be verified. This is minor since these are supplementary citations, not the core reduction reference.

Result: Pass.

Well-written

Several issues found:

4a/4c — Overhead table field name mismatch:
The overhead table lists num_cities as a target metric, but the actual TravelingSalesman model has size fields num_vertices and num_edges (confirmed via pred show TravelingSalesman --json). There is no num_cities getter on the TSP type. The bound field also does not exist as a size field. The overhead table should be:

Target metric	Formula
num_vertices	num_vertices
num_edges	num_vertices * (num_vertices - 1) / 2

4a — Satisfaction-to-optimization type mismatch not addressed:
HamiltonianCircuit is a decision/satisfaction problem (does a Hamiltonian circuit exist?), while TravelingSalesman is an optimization problem (minimize tour weight). The issue describes setting B = n as a "bound," but the codebase's TSP implementation is an optimization problem (Direction::Minimize) with edge-selection variables, not a decision problem with a bound parameter. The reduction algorithm does not explain how to handle this mismatch in the codebase's framework. Specifically:

• TSP uses binary variables per edge (select/not-select), not a city permutation
• The "bound" B = n has no representation in the TSP model — the model minimizes total weight, it does not check against a threshold
• Solution extraction (from TSP edge selection back to Hamiltonian circuit) is not clearly specified in terms of the actual codebase representation

4d — Example quality:
The example is well-constructed (triangular prism, 6 vertices, fully worked distance matrix, two valid solutions shown). This part is good.

Result: Fail — the overhead table uses incorrect field names, and the reduction algorithm does not address the satisfaction-vs-optimization type mismatch in the actual codebase implementation.

Recommendations

• Add or reference a companion [Model] issue for HamiltonianCircuit before this rule can be implemented.
• Rewrite the overhead table to use num_vertices and num_edges (the actual TSP size fields).
• Clarify how the reduction works with the codebase's optimization-based TSP model. Since TSP minimizes total weight, the reduction produces a TSP instance where the optimal tour has weight n iff the source graph has a Hamiltonian circuit. Solution extraction maps the TSP edge selection directly to a Hamiltonian circuit (all selected edges with weight 1 form the circuit in G).
• Consider whether HamiltonianCircuit should be a satisfaction problem (Metric = bool) or modeled differently. The reduction needs to clearly state how a satisfaction-problem source maps to an optimization-problem target.

[GiggleLiu]

Fix-issue changelog

• Updated metadata: source_in_codebase: false → true (HamiltonianCircuit now exists in pred)
• Updated canonical names to CamelCase (HamiltonianCircuit, TravelingSalesman)
• Reframed reduction algorithm from decision (bound B = n) to optimization (optimal tour weight = n iff HC exists), consistent with codebase sat→opt patterns
• Added representation note: HC uses vertex permutation, TSP uses binary edge selection; solution extraction traverses selected edges to recover cycle ordering
• Fixed overhead table: num_cities → num_vertices, removed invalid bound row, cleaned up num_edges parenthetical
• Reframed example: removed bound references, added extracted HC solutions as vertex permutations
• Updated validation method to use optimization language

Applied by /fix-issue.