Repository navigation
[Rule] HamiltonianCircuit to TravelingSalesman #258
Description
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:
-
Graph: Construct the complete graph K_n on vertex set V with n(n-1)/2 edges.
-
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)
-
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.
-
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_verticesof source HamiltonianCircuit instance (|V|) - m =
num_edgesof 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.
Activity
zazabap commentedon Mar 11, 2026
Issue Quality Check — Rule
num_citieswhich is not a valid TSP size field; type mismatch between satisfaction and optimization problemOverall: 1 passed, 1 warning, 1 failed
Usefulness
The source problem HamiltonianCircuit does not exist in the codebase (
pred show HamiltonianCircuitfails). The issue metadata correctly notessource_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:
This is a classic NP-completeness reduction with a non-trivial distance gadget. Pass.
Correctness
Reference verification:
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_citiesas a target metric, but the actual TravelingSalesman model has size fieldsnum_verticesandnum_edges(confirmed viapred show TravelingSalesman --json). There is nonum_citiesgetter on the TSP type. Theboundfield also does not exist as a size field. The overhead table should be:num_verticesnum_verticesnum_edgesnum_vertices * (num_vertices - 1) / 24a — 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: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
[Model]issue for HamiltonianCircuit before this rule can be implemented.num_verticesandnum_edges(the actual TSP size fields).Metric = bool) or modeled differently. The reduction needs to clearly state how a satisfaction-problem source maps to an optimization-problem target.[-][Rule] HAMILTONIAN CIRCUIT to TRAVELING SALESMAN[/-][+][Rule] HamiltonianCircuit to TravelingSalesman[/+]GiggleLiu commentedon Mar 21, 2026
Fix-issue changelog
source_in_codebase: false→true(HamiltonianCircuit now exists in pred)HamiltonianCircuit,TravelingSalesman)num_cities→num_vertices, removed invalidboundrow, cleaned upnum_edgesparentheticalApplied by
/fix-issue.Add plan for #258: [Rule] HamiltonianCircuit to TravelingSalesman
Implement #258: [Rule] HamiltonianCircuit to TravelingSalesman
GiggleLiu commentedon Mar 22, 2026
Please kindly check the following items (PR #745):
predcommands💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.
Fix #258: [Rule] HamiltonianCircuit to TravelingSalesman (#745)