Hamiltonian Cycle Problem

The Hamiltonian cycle (HCP) problem is the problem of determining whether a Hamiltonian cycle (

HCP is NP-complete and it is a special case of the traveling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance traveled is equal to the number of vertices.

An introduction on NP-complete Problems and the Hamiltonian Cycle Problem

The Hamiltonian cycle (HCP) problem is the problem of determining whether a Hamiltonian cycle (

*a cycle in an undirected or directed graph that visits each vertex exactly once*) exists in a given graph (whether directed or undirected).HCP is NP-complete and it is a special case of the traveling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance traveled is equal to the number of vertices.

**Learning Resources:**An introduction on NP-complete Problems and the Hamiltonian Cycle Problem

**Algorithms:***Snakes and Ladders algorithm v2.49 for the Hamiltonian Cycle Problem*
Download links for SLH2: Windows - Linux

Related article:

Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem.

See downloads page.

Related article:

Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem.

*Mathematical Programming Computation*, 6(1), 55-75.

**Benchmark sets:**

See downloads page.