[Model] HamiltonianCycle

[isPANN]

Definition

• Name: HamiltonianCycle
• Category: graph
• Reference: Garey & Johnson (1979), Problem [GT37]; Wikipedia

Given an undirected graph G=(V,E) where V is the vertex set and E is the edge set,
and edge weights w: E → R, find a cycle that visits every vertex in V exactly once
and returns to the starting vertex, minimizing the total edge weight.

A Hamiltonian cycle is a sequence (v_0, v_1, ..., v_{n-1}) where:

• Every vertex appears exactly once
• (v_i, v_{i+1 mod n}) ∈ E for all i
• The total cost is Σ_i w(v_i, v_{i+1 mod n})

Variables

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

Validity requires: exactly 2 selected edges incident to each vertex (degree constraint),
selected edges form a single connected cycle (no subtours),
and exactly |V| edges are selected.

Schema

Type name: HamiltonianCycle

Field	Description
graph	The graph G=(V,E)
edge_weights	A weight w(e) for each edge e ∈ E

What could vary across variants:

• Graph topology — the problem makes sense on general graphs, grid graphs, unit disk graphs, etc.
• Weights — could be unweighted (decision: does a cycle exist?) or numeric (optimization: find cheapest cycle).

Problem size is characterized by:

• number of vertices
• number of edges

Complexity

• Decision complexity: NP-complete (Karp, 1972)
• Best known exact algorithm: O(2^n · n^2) by Held-Karp dynamic programming
• Best known approximation: 3/2-approximation for metric TSP (Christofides, 1976)

Example Instances

Instance 1: K4 complete graph (has solution)

Vertices: 4
Edges: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)
Weights: 10, 15, 20, 35, 25, 30

Optimal cycle: 0→1→3→2→0, cost = 10+25+30+15 = 80.

Instance 2: Path graph (no solution)

Vertices: 4
Edges: (0,1), (1,2), (2,3)
Weights: 1, 1, 1

No valid Hamiltonian cycle exists (vertex 0 and 3 have degree 1).

Instance 3: Cycle graph C5 (unique solution)

Vertices: 5
Edges: (0,1), (1,2), (2,3), (3,4), (4,0)
Weights: 1, 1, 1, 1, 1

The only Hamiltonian cycle uses all 5 edges, cost = 5.

Instance 4: K_{2,3} bipartite (no solution)

Vertices: 5 (partition A={0,1}, B={2,3,4})
Edges: (0,2), (0,3), (0,4), (1,2), (1,3), (1,4)

No Hamiltonian cycle exists (unequal partition sizes).

Batch Test Data (optional)

Python networkx can check Hamiltonian cycles on small graphs:

import networkx as nx
from itertools import permutations

def has_hamiltonian_cycle(G):
    """Brute-force check for small graphs."""
    nodes = list(G.nodes())
    n = len(nodes)
    for perm in permutations(nodes[1:]):  # fix first node
        cycle = [nodes[0]] + list(perm)
        if all(G.has_edge(cycle[i], cycle[(i+1) % n]) for i in range(n)):
            return True, cycle
    return False, None

Generate random graphs with nx.gnp_random_graph(n, p) for n ≤ 8.