[Model] HamiltonianCircuit

[isPANN]

Motivation

HAMILTONIAN CIRCUIT from Garey & Johnson, A1.3 GT37. A classical NP-complete problem (Karp, 1972) central to the theory of NP-completeness. It is a fundamental source problem for reductions to HAMILTONIAN PATH, TRAVELING SALESMAN, and many other combinatorial problems.

Definition

Name: HamiltonianCircuit
Canonical name: HAMILTONIAN CIRCUIT (also: Hamiltonian Cycle)
Reference: Garey & Johnson, Computers and Intractability, A1.3 GT37

Mathematical definition:

INSTANCE: Graph G = (V, E).
QUESTION: Does G contain a Hamiltonian circuit, i.e., a closed path that visits every vertex exactly once?

Variables

• Encoding: Permutation encoding — each variable represents a position in the circuit and takes a vertex index as its value.
• Count: n = |V| variables (one per position in the circuit).
• Per-variable domain: each variable takes a value in {0, 1, ..., n−1} (which vertex occupies that position). dims() = vec![n; n].
• Meaning: The variable assignment encodes a permutation π of the vertices, representing the order in which they are visited. A satisfying assignment is a permutation π such that (1) all values are distinct (a valid permutation), and (2) {π(i), π(i+1 mod n)} ∈ E for all i ∈ {0, ..., n−1}.

Schema (data type)

Type name: HamiltonianCircuit
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph on which a Hamiltonian circuit is sought

Size fields:

• num_vertices() → usize — number of vertices (|V|)
• num_edges() → usize — number of edges (|E|)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed (the question is purely structural).
• Specializations: planar graphs, bipartite graphs, cubic graphs (all remain NP-complete per GJ comments).

Complexity

• Best known exact algorithm: O*(1.657^n) randomized time via the "Determinant Sums" Monte Carlo algorithm (Björklund, 2010/2014). For bipartite graphs this improves to O*(1.415^n) ≈ O*(√2^n). For graphs of maximum degree 3, a backtracking search achieves O*(1.251^n) (Iwama & Nakashima, 2007, COCOON, LNCS 4598).
• Classic algorithm: O(n^2 · 2^n) deterministic dynamic programming (Held-Karp / Bellman, 1962) — this is the standard reference complexity used for the general case. Use "2^num_vertices" in declare_variants! (matches existing TSP convention; polynomial factors are dropped).
• NP-completeness: NP-complete (Karp, 1972, "Reducibility Among Combinatorial Problems").
• References:
  • R.M. Karp (1972). "Reducibility Among Combinatorial Problems." Complexity of Computer Computations, pp. 85–103. Plenum Press.
  • M. Held and R.M. Karp (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210.
  • A. Björklund (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing, 43(1):280–299. [arXiv:1008.0541]
  • K. Iwama and T. Nakashima (2007). "An Improved Exact Algorithm for Cubic Graph TSP." COCOON 2007, LNCS 4598, pp. 108–117. O*(1.251^n) for cubic graphs.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E).
QUESTION: Does G contain a Hamiltonian circuit?

Reference: [Karp, 1972]. Transformation from VERTEX COVER (see Chapter 3).
Comment: Remains NP-complete (1) if G is planar, cubic, 3-connected, and has no face with fewer than 5 edges [Garey, Johnson, and Tarjan, 1976a], (2) if G is bipartite [Krishnamoorthy, 1975], (3) if G is the square of a graph [Chvátal, 1976], and (4) if a Hamiltonian path for G is given as part of the instance [Papadimitriou and Stieglitz, 1976]. Solvable in polynomial time if G has no vertex with degree exceeding 2 or if G is an edge graph (e.g., see [Liu, 1968]). The cube of a non-trivial connected graph always has a Hamiltonian circuit [Karaganis, 1968].

How to solve

• It can be solved by (existing) bruteforce — enumerate all permutations of vertices and check if consecutive pairs (and wrap-around) are edges.
• It can be solved by reducing to integer programming.
• Other: Held-Karp dynamic programming in O(n^2 · 2^n) time and O(n · 2^n) space; Björklund's randomized algorithm in O*(1.657^n).

Example Instance

Instance 1 (has Hamiltonian circuit):
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}
• (Prism graph / triangular prism: two triangles {0,1,2} and {3,4,5} with matching edges)
• Hamiltonian circuit exists: 0 → 1 → 2 → 5 → 4 → 3 → 0
• Answer: YES

Instance 2 (no Hamiltonian circuit):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges: {0,1}, {0,2}, {0,3}, {0,4}, {0,5}, {1,2}, {3,4}
• (Star K_{1,5} plus two extra chords — vertex 0 has degree 5, but the graph is not "balanced")
• Any Hamiltonian circuit must alternate between vertex 0 and others, but after leaving 0 to reach 1, returning requires using 0 again — impossible to visit all without revisiting 0.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; enables key Karp reductions
Non-trivial	✅ Pass	Distinct satisfaction problem with unique feasibility constraints
Correctness	⚠️ Warn	References verified; minor inaccuracy in variable description
Well-written	⚠️ Warn	Variable section is confusing; minor reasoning gap in Example 2

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. HamiltonianCircuit does not exist in the codebase (confirmed via pred show HamiltonianCircuit). The problem is one of Karp's original 21 NP-complete problems (#10 Undirected Hamiltonian Circuit) and GJ number GT37. It is a natural source for reductions to TravelingSalesman (already in the codebase) and a natural target from MinimumVertexCover via Feedback Node Set and Directed Hamiltonian Circuit (per Karp's reduction tree). The motivation section correctly identifies these connections.

Non-trivial

Pass. HamiltonianCircuit has genuinely distinct feasibility constraints from all 24 existing problems. It is a satisfaction (decision) problem asking whether a graph contains a cycle visiting every vertex exactly once. No existing problem in the codebase captures this constraint structure — TravelingSalesman is the closest but is an optimization problem over weighted complete graphs, which is fundamentally different.

Correctness

Warn — minor issues, but no outright errors.

References verified:

• Karp (1972) — "Reducibility Among Combinatorial Problems," Complexity of Computer Computations, pp. 85-103. Already in references.bib as karp1972. Correctly cited.
• Held & Karp (1962) — "A dynamic programming approach to sequencing problems," JSIAM 10(1):196-210. Already in references.bib as heldkarp1962. The O(n^2 * 2^n) complexity bound is correct.
• Bjorklund (2014) — "Determinant Sums for Undirected Hamiltonicity," SIAM Journal on Computing 43(1):280-299 [arXiv:1008.0541]. Confirmed via SIAM and arXiv. The O*(1.657^n) randomized bound is correct. The bipartite improvement to O*(1.415^n) is also correct.

Minor inaccuracy: The issue states "O*(1.251^n) for graphs of maximum degree 3 via backtracking search" without a citation. This specific bound should include a reference (e.g., Eppstein 2007 or Iwama & Nakashima 2007) for verifiability.

Complexity for declare_variants!: The issue suggests using the Held-Karp O(n^2 * 2^n) bound as the "standard reference complexity for the general case." This is a reasonable conservative choice since it is deterministic, but the Bjorklund O*(1.657^n) bound is strictly better (albeit randomized). Either is defensible; the implementer should decide.

Well-written

Warn — mostly complete but with two issues to address.

Template completeness: All required sections are present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance. No placeholders.

Issue 1 — Variable description is contradictory: The Variables section begins with "n = |V| binary variables" but then immediately describes a permutation encoding with "position index in {0, 1, ..., n-1}." These are incompatible — a binary encoding uses n binary variables (0/1), while a permutation encoding uses n variables each with domain {0,...,n-1}. For a satisfaction problem with dims() returning the per-variable domain sizes, this distinction matters for implementation. Recommendation: clarify that the natural encoding is a permutation (n variables, each with domain size n), or alternatively describe a binary matrix encoding (n^2 binary variables).

Issue 2 — Example 2 reasoning: The explanation for why Instance 2 has no Hamiltonian circuit says "after leaving 0 to reach 1, returning requires using 0 again." The simpler and more rigorous argument is that vertex 5 has degree 1 (connected only to vertex 0), and any Hamiltonian circuit requires every vertex to have degree at least 2. The current explanation is not wrong but is needlessly indirect and could confuse implementers.

Notation consistency: Symbols are generally consistent across sections. The Schema table correctly identifies this as a SatisfactionProblem with Metric = bool. The field name graph with type SimpleGraph is appropriate and consistent with existing graph problems.

Example quality: Both examples are good — Instance 1 (prism graph, 6 vertices, 9 edges) is non-trivial and brute-force verifiable. The worked Hamiltonian circuit 0→1→2→5→4→3→0 is correct (all edges verified). Instance 2 correctly has no Hamiltonian circuit.

Recommendations

• Fix the Variables section to use a consistent encoding (permutation with domain size n, or n^2 binary variables).
• Add a citation for the O*(1.251^n) degree-3 claim.
• Simplify Instance 2's explanation: "Vertex 5 has degree 1, but every vertex in a Hamiltonian circuit must have degree >= 2."

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; distinct from TravelingSalesman
Non-trivial	✅ Pass	Decision (satisfaction) problem with different trait from existing TSP (optimization)
Correctness	✅ Pass	All three references verified; complexity bounds match the literature
Well-written	⚠️ Warn	Variables section is confused about encoding; minor notation issues

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

HamiltonianCircuit does not exist in the current codebase (pred show HamiltonianCircuit fails). The closest problem is TravelingSalesman, but that is an optimization problem (OptimizationProblem with Metric = SolutionSize<W>) seeking the minimum-weight Hamiltonian cycle, whereas HamiltonianCircuit is a satisfaction problem (SatisfactionProblem with Metric = bool) asking whether any Hamiltonian circuit exists. These implement different traits and serve different roles in the reduction graph.

The motivation correctly identifies HamiltonianCircuit as a classical source problem for reductions to Hamiltonian Path, TSP, and other combinatorial problems — it is one of Karp's original 21 NP-complete problems (#10).

Non-trivial

HamiltonianCircuit has genuinely different feasibility semantics from all 24 existing problems. It is not a variant of TravelingSalesman (different trait hierarchy), nor is it isomorphic to any existing decision problem in the codebase. The feasibility constraint (closed path visiting every vertex exactly once) is structurally distinct.

Correctness

References verified:

1. Karp (1972) — Already in the project bibliography as karp1972. The claim that Hamiltonian Circuit is NP-complete (from Karp's original 21 problems) is correct.

2. Held & Karp (1962) — Already in the bibliography as heldkarp1962. The O(n^2 * 2^n) dynamic programming bound is the standard reference complexity. Correct.

3. Björklund (2014) — "Determinant Sums for Undirected Hamiltonicity," SIAM J. Comput., 43(1):280-299. Verified on SIAM and arXiv:1008.0541. The O*(1.657^n) randomized bound and O*(sqrt(2)^n) ≈ O*(1.414^n) bipartite bound are correct.

4. Degree-3 graphs: O*(1.251^n) — This bound is from Iwama & Nakashima (2007), improving Eppstein's (2003) O*(1.260^n). The issue does not cite a specific paper for this claim but the bound itself is correct.

Garey & Johnson excerpt in the "Extra Remark" section is consistent with GT37 in the book.

Well-written

Strengths:

• Definition section is clear and mathematically well-formed
• Schema section correctly identifies this as a SatisfactionProblem with Metric = bool
• Both examples are non-trivial, correct, and fully worked
• Complexity section is thorough with multiple algorithm variants

Issues (warnings, not failures):

1. Variables section is confused about encoding. The section mixes three different encodings (permutation, bitmask-DP, and "n binary variables") without committing to the one that will actually be implemented. For a SatisfactionProblem in this codebase, dims() must return a concrete vector. For a permutation encoding, dims() would be vec![n; n] (each slot picks a vertex index). For a binary selection encoding (as used in TSP), it would be something else entirely. The issue should clarify which encoding will be used and align the Variables section accordingly.

2. The "n binary variables" claim contradicts the permutation description. The opening says "n = |V| binary variables" but then immediately says "position index in {0, 1, ..., n-1}" which is an n-ary domain, not binary.

3. Missing size_fields specification. The Schema section should explicitly list the size fields (getter methods) that will be available, e.g., num_vertices, num_edges. These are needed for overhead expressions in future reduction rules.

4. Degree-3 complexity claim uncited. The 1.251^n bound for cubic graphs is stated without attribution (it is from Iwama & Nakashima, 2007).

Recommendations

• Settle on a single variable encoding and make dims() consistent with it. A permutation encoding with dims() = vec![n; n] would be natural, or alternatively a binary edge-selection encoding.
• Add size_fields: [num_vertices, num_edges] to the Schema section.
• Cite Iwama & Nakashima (2007) for the cubic graph bound, or Eppstein (2003) for the original O*(1.260^n).
• The declare_variants! complexity string for the general case should use the Held-Karp bound "num_vertices^2 * 2^num_vertices" (deterministic) rather than Björklund's randomized bound, unless the project policy is to use randomized algorithms.