[Discussion] Hamiltonian Path, Hamiltonian Circuit, and Traveling Salesman — models and reduction triviality

[zazabap]

Context

The codebase currently has TravelingSalesman<G, W> (originally implemented as HamiltonianCycle, then renamed). Several open issues reference Hamiltonian Circuit (#519, #520) and Hamiltonian Path (#432, #433, #435, #436) as source problems for reductions to other targets, but neither exists as a standalone model yet.

This issue discusses whether we need separate models and how trivial the reductions between them are.

Problem Definitions

Problem	Visits all vertices	Returns to start	Weighted / Optimization
Hamiltonian Path	Yes	No	No (decision: does such a path exist?)
Hamiltonian Circuit	Yes	Yes	No (decision: does such a circuit exist?)
Traveling Salesman	Yes	Yes	Yes (minimize total edge weight)

• Hamiltonian Path: Given graph G, does there exist a path visiting every vertex exactly once?
• Hamiltonian Circuit (Cycle): Given graph G, does there exist a cycle visiting every vertex exactly once?
• Traveling Salesman (TSP): Given a weighted graph G, find the minimum-weight Hamiltonian circuit.

Do We Need Separate Models?

The current TravelingSalesman subsumes Hamiltonian Circuit (set all weights to 1, check if optimal tour cost = n). But:

1. Hamiltonian Circuit is a SatisfactionProblem (Metric = bool), while TravelingSalesman is an OptimizationProblem. They have different trait implementations and solver interfaces (find_satisfying vs find_best).
2. Hamiltonian Path is structurally different — no return-to-start requirement, different configuration space.
3. Multiple open issues ([Rule] Hamiltonian Circuit to Feasible Basis Extension #519, [Rule] Hamiltonian Circuit to Traveling Salesman Polytope Non-Adjacency #520, [Rule] Hamiltonian Path to Consecutive Ones Submatrix #432, [Rule] Hamiltonian Path to Consecutive Block Minimization #435, [Rule] Hamiltonian Path to Consecutive Sets #436) reference these as source problems for reductions, so they need to exist as concrete types.

Proposal: Add two new models:

• HamiltonianCircuit<G> — SatisfactionProblem on graphs, binary variable per edge
• HamiltonianPath<G> — SatisfactionProblem on graphs, binary variable per edge

Reductions Between Them

Hamiltonian Circuit → Traveling Salesman

Triviality: Near-trivial (embedding). Given graph G, create TSP instance with weight 1 for edges in G and weight n+1 for non-edges (on complete graph). G has a Hamiltonian circuit iff optimal TSP cost = n. This is a standard textbook reduction but requires constructing the complete graph and choosing weights — not a mere type cast.

Hamiltonian Path → Hamiltonian Circuit

Triviality: Simple but non-trivial. Add a dummy vertex connected to all existing vertices. G has a Hamiltonian path iff the augmented graph has a Hamiltonian circuit (the dummy vertex "closes" the path). Overhead: 1 extra vertex, n extra edges. Simple construction, but real work is done.

Hamiltonian Path → Traveling Salesman

Triviality: Simple, composes the above two. Add dummy vertex + complete graph construction + weight assignment. Could be implemented directly or as a composite reduction.

Hamiltonian Circuit → Hamiltonian Path

Triviality: Slightly more involved. For each edge (u,v) in G, check if G minus (u,v) has a Hamiltonian path from u to v. This is a Turing reduction (polynomial number of oracle calls), not a single many-one reduction. A many-one reduction exists but requires gadget construction. Less trivial than the reverse direction.

Questions for Discussion

1. Should HamiltonianCircuit be a thin wrapper around TravelingSalesman (delegating to it internally) or a fully independent model?
2. For the Path → Circuit reduction (dummy vertex), is O(n) overhead small enough to warrant a "simple" label, or should we treat it like any other rule?
3. Should we implement the direct Path → TSP reduction, or rely on the composite path Path → Circuit → TSP?
4. Are there other reductions from/to these problems we should prioritize?

References

• Garey & Johnson, Computers and Intractability, problems GT37 (Hamiltonian Path), GT38 (Hamiltonian Circuit), ND22 (TSP)
• Karp (1972), "Reducibility Among Combinatorial Problems" — includes Hamiltonian Circuit

[GiggleLiu]

For the discussion questions:

1. HC should NOT be a wrapper around TSP. They implement different traits (SatisfactionProblem vs OptimizationProblem) with different encodings — HC uses permutation-based (vec![n; n]) per issue [Model] HamiltonianCircuit #216, TSP uses edge-binary (vec![2; num_edges]). Separate models is the right call.

2. HC → TSP reduction is non-trivial despite the conceptual closeness — it requires constructing the complete graph and translating between permutation and edge-binary encodings. Worth implementing as a proper reduction rule.

3. Path → Circuit → TSP composite seems cleaner than a direct Path → TSP reduction, since the individual steps are well-understood and simpler to verify.

PR #619 implements HC as a standalone SatisfactionProblem with permutation encoding. This aligns with the proposal here.