  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 only a linear function of that of the original
instance. This is achieved by first considering various restrictions of HCP.
Known conversions from directed HCP to undirected HCP, and sub-cubic HCP to
cubic HCP are given. We introduce a subgraph called a 4-gate and show that it
may be used to convert sub-quartic HCP into sub-cubic HCP. We further
generalise this idea by first introducing the 5-gate, and then the s-gate for
any s >= 4. We prove that these subgraphs may be used to convert general
instances of HCP into cubic HCP instances, where the input size of the
converted instance is a quadratic function of that of the original instance.
This result improves upon the previously best known approach which results in
cubic growth in the size of the instance. We further prove that the quadratic
function is reduced to a linear function if the maximum initial degree is
bounded above by a constant. Motivated by this result, we describe an algorithm
to convert general HCP to HCP of bounded degree and prove that it results in
only linear growth. All of the above results are then used in the proof that
any instance of HCP may be converted to an equivalent instance 3HCP with only
linear growth in the input size.
