A Linear-size Conversion of HCP to 3HCP

Vladimir Ejov, Michael Haythorpe, Serguei Rossomakhine

We provide an algorithm that converts any instance of the Hamiltonian cycle problem (HCP) into a cubic instance of HCP (3HCP), and prove that the input size of the new instance is…