🧩 Constraint Solving POTD:Problem of the Day: Hamiltonian Circuit Problem

[github-actions[bot]]

Problem Statement

The Hamiltonian Circuit Problem asks: given an undirected graph, does there exist a cycle that visits each vertex exactly once and returns to the starting vertex?

This is a decision problem (unlike the Traveling Salesman Problem, which is an optimization problem). We're asking "can we find such a tour?" not "what's the minimum cost tour?"

Concrete Instance

Consider a graph with 5 vertices representing cities: A, B, C, D, E.
Edges (connections) exist between:

• A–B, A–C, A–D
• B–C, B–E
• C–D, C–E
• D–E

Question: Is there a Hamiltonian circuit starting from A, visiting B, C, D, E each exactly once, and returning to A?

Solution: Yes! One valid circuit is: A → B → E → D → C → A.

Input/Output Spec:

• Input: Graph G = (V, E) with |V| = n vertices
• Output: YES if a Hamiltonian circuit exists; NO otherwise. (Optionally, return the circuit itself.)

---

Why It Matters

Verification and access control: Network security teams model trusted communication paths as Hamiltonian circuits; verifying that all devices in a sensor network can reach each other in a single loop is a real accessibility problem.

Manufacturing and inspection: Automated inspection systems must visit each station on a production line exactly once; the Hamiltonian circuit problem models whether a feasible inspection route exists.

Board game design: Game designers use Hamiltonian circuits to create interesting board layouts where every square is visited exactly once in a single traversal, fundamental to puzzles like the Knight's Tour.

---

Modeling Approaches

Approach 1: Constraint Programming (Decision-Focused)

Paradigm: Constraint Logic Programming or CP solver (e.g., Gecode, Choco, OR-Tools)

Decision variables:

• x[v][u] ∈ {0, 1} for each edge (v, u): 1 if the edge is in the circuit, 0 otherwise

Constraints:

1. Degree constraint: Each vertex has exactly 2 incident edges

   ∀v ∈ V: Σ_{u ∈ neighbors(v)} x[v][u] = 2
   

2. Connectivity constraint (subtour elimination): The selected edges form one connected component, not multiple disjoint cycles

   ∀S ⊂ V, 2 ≤ |S| < n:
   Σ_{(u,v) ∈ S} x[u][v] ≤ |S| - 1
   

Solving approach: Arc consistency propagation on degree constraints, then branch-and-bound or DFS with backtracking. Subtour elimination constraints are checked dynamically; when a subtour is detected, add a cutting plane.

Trade-offs: Tight formulation but exponentially many subtour constraints (can be added dynamically). Propagates well; scalable to ~100 vertices with good heuristics.

---

Approach 2: SAT Encoding

Paradigm: Boolean Satisfiability (SAT)

Decision variables:

• x[t][v][u] ∈ {true, false}: true if edge (v, u) is traversed at step t (t = 0, 1, ..., n-1)

Clauses (CNF):

1. Exactly-once vertex: Each vertex visited at exactly one step

   ∀v ∈ V: (Σ_{t=0}^{n-1} x[t][v][u] for all u) = 1
   

   (Encoded as 1-hot constraint in CNF using auxiliary variables)

2. Step connectivity: At step t, exactly one edge is active

   ∀t ∈ {0..n-1}: Σ_{(v,u) ∈ E} x[t][v][u] = 1
   

3. Vertex ordering: Next vertex must be a neighbor

   ∀t, v, u: x[t][v][u] ∧ ¬adjacent(v, u) → false
   

Solving approach: Modern SAT solvers (CDCL with learned clauses). Linear encoding size, but many clauses. Benefits from conflict-driven learning.

Trade-offs: Highly parallelizable encoding; leverages decades of SAT-solver optimization. Larger CNF size than CP, but often faster on large instances due to mature CDCL heuristics.

---

Key Techniques

1. Degree Constraint Propagation

The constraint ∀v: degree(v) = 2 is very strong. As edges are chosen or eliminated, unit propagation can deduce must-include or must-exclude edges. CP solvers use arc consistency algorithms (AC-3) to efficiently prune the domain.

2. Subtour Elimination and Cut Generation

Once a partial solution is found, check for subtours (cycles not including all vertices). If detected, a cutting plane (new constraint) rules out that subtour. This is similar to integer linear programming techniques and is often done dynamically within branch-and-bound.

3. Symmetry Breaking

Hamiltonian circuits have rotational symmetry: A → B → C → A is the same as B → C → A → B. To reduce search space, fix the starting vertex (say, always start at vertex 1) and optionally impose a canonical direction (e.g., next neighbor is always > current, breaking direction reversal).

---

Challenge Corner

Question for readers: The Hamiltonian circuit problem is NP-complete, but some special graph classes (like planar graphs or bipartite graphs with certain properties) admit polynomial-time algorithms. Can you think of a graph structure where finding a Hamiltonian circuit becomes easier? Hint: consider the degree of each vertex.

Extension: How would you modify the problem to handle weighted edges and find the shortest Hamiltonian circuit (i.e., the TSP solution)? What new techniques would you add to your solver?

---

References

1. Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. — Classic reference for Hamiltonian circuit complexity.

2. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier. Chapter on SAT and global constraints provides encoding and propagation details.

3. Concorde TSP Solver documentation ((www.math.uwaterloo.ca/redacted) — Although focused on TSP, the Concorde solver tackles Hamiltonian circuits as a subproblem; excellent reference for cutting-plane techniques.

4. Hooker, J. N. (2012). Integrated Methods for Optimization. Springer. — Good coverage of hybrid CP/MIP approaches to graph problems like Hamiltonian circuits.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.09 AIC · ⌖ 5.28 AIC · ⊞ 6K · ◷

• expires on Oct 3, 2026, 3:32 AM UTC-08:00