[Model] HamiltonianCycle (Decision Version)

[QingyunQian]

Motivation

Add the decision version of Hamiltonian Cycle, one of Karp's 21 NP-complete problems. Complements the existing TravelingSalesman (optimization version) and enables classic reductions from 3-SAT and other decision problems.

Definition

Name: HamiltonianCycle
Reference:

• Karp, R. M. (1972). "Reducibility among combinatorial problems." In Complexity of Computer Computations.
• Garey & Johnson (1979), "Computers and Intractability", Problem [GT37]
• https://en.wikipedia.org/wiki/Hamiltonian_path_problem

Given an undirected graph G=(V,E) where V is the vertex set and E is the edge set, determine whether there exists a simple cycle C that visits every vertex exactly once. Formally, does there exist a permutation (v₁, v₂, ..., vₙ) of V such that (vᵢ, vᵢ₊₁) ∈ E for all i ∈ {1, ..., n-1}, (vₙ, v₁) ∈ E, and all vertices are distinct?

Note: This is the decision version (returns bool), distinct from TravelingSalesman which is the optimization version (returns minimum weight). Issue #47 implemented the optimization version.

Variables

• Count: m = |E| (one variable per edge)
• Per-variable domain: binary {0, 1}
• Meaning: xₑ = 1 if edge e is in the Hamiltonian cycle, 0 otherwise

Schema (data type)

Type name: HamiltonianCycle
Variants: graph topology (SimpleGraph, PlanarGraph, BipartiteGraph, etc.)

Field	Type	Description
graph	G	The undirected graph G=(V,E)

Complexity

• Classic exact algorithm: O(2ⁿ · n²) by Bellman-Held-Karp dynamic programming (1962), where n = |V|
• References:
  • Held, M., & Karp, R. M. (1962). "A dynamic programming approach to sequencing problems." Journal of SIAM, 10(1), 196-210.
  • Woeginger, G. J. (2003). "Exact algorithms for NP-hard problems: A survey."

Extra Remark

Relationship to TravelingSalesman:

• TravelingSalesman (Issue [Model] HamiltonianCycle #47): OptimizationProblem, finds minimum-weight Hamiltonian cycle
• HamiltonianCycle (this issue): SatisfactionProblem, determines if any Hamiltonian cycle exists
• Both use edge-based binary variables, but this returns bool instead of SolutionSize<W>

Historical significance: One of Karp's original 21 NP-complete problems (1972), fundamental in computational complexity theory.

Special cases:

• NP-complete even for planar graphs with max degree 3, bipartite graphs, grid graphs

Implementation notes: Should implement SatisfactionProblem trait. Can reuse validation logic from TravelingSalesman::is_valid_hamiltonian_cycle().

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to TravelingSalesman: HC exists iff TSP with unit weights has optimal cost = n.
• Other: Can be reduced to SAT (future work).

Example Instance

Instance 1: Hypercube graph Q₃ (YES)

• Graph: 3D Cube graph with |V|=8, |E|=12, 3-regular
• Edges: Bottom face (0-1, 1-2, 2-3, 3-0), Top face (4-5, 5-6, 6-7, 7-4), Pillars (0-4, 1-5, 2-6, 3-7)
• Answer: YES (Hamiltonian cycle exists)
• Example cycle: 0→1→2→3→7→6→5→4→0

Instance 2: Path graph P₄ (NO)

• Graph: Path with 4 vertices: 0-1-2-3
• Answer: NO (endpoints have degree 1, cannot form a cycle)

[isPANN]

Closing as duplicate — this problem is covered by the Garey & Johnson extraction (P06 HamiltonianCircuit, G&J Chapter 3, Section 3.1.3). 'Hamiltonian Cycle' and 'Hamiltonian Circuit' are the same problem. The extracted reference issue in references/Garey&Johnson/issues/models/P06_hamiltonian_circuit.md provides a comprehensive definition from the original source.