Generating Hard Instances of the Hamiltonian Cycle Problem via Degree Distribution Optimization
Hamiltonian Cycle Problem, Instance Hardness, Surrogate Objective, Mixed-Integer Quadratic Programming
In this work, we investigate the Hamiltonian Cycle Problem (HCP) from the perspective of instance difficulty. Although no polynomial-time algorithm is known for NP-complete problems, state-of-the-art HCP algorithms efficiently solve most random instances, including those near the hamiltonicity phase transition. In contrast, the hardest known instances are highly structured, non-Hamiltonian, and dense. These instances were generated using expensive evolutionary algorithms that directly maximized the number of recursive calls made by a state-of-the-art HCP solver. While the instances can be reproduced once the underlying structure is known, this approach offers limited insight into what features drive hardness. We propose an efficient method for generating hard HCP instances by optimizing a surrogate objective based on degree distribution statistics. We introduce two approaches: (1) an exact MIQP model that maximizes degree variance alone, serving as a baseline, and (2) a heuristic (the VM Heuristic) that simultaneously maximizes variance and minimizes median degree using a multi-start hillclimber with edge swaps. Given a fixed number of vertices, the VM Heuristic reproduces all known hardest instances and generates new ones across a wide range of edge counts. Our analysis reveals a previously unreported threshold at m = 4(n - 3), where instances exhibit an abrupt change from low to high recursion counts, growing exponentially beyond this threshold. These results provide insight into the structural features that drive HCP hardness and enable efficient generation for future research.