zbMATH — the first resource for mathematics

A linear-size conversion of HCP to 3HCP. (English) Zbl 1321.05144
Summary: 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 result is reminiscent of the famous SAT to 3SAT conversion by R. M. Karp [Kibern. Sb., Nov. Ser. 12, 16–38 (1975); translation from Complexity of Computer Computations 1972, Plenum Press, New York, 85–103 (1973; Zbl 0366.68041)]. Known conversions from directed HCP to undirected HCP, and sub-cubic HCP to cubic HCP are given. We introduce a new subgraph called a 4-gate and provide a procedure that converts any sub-quartic instance of HCP to a sub-cubic instance. Finally, we describe a procedure to convert any graph to a sub-quartic graph, and use the previous results to provide an algorithm which converts HCP to 3HCP with only linear growth in the instance size.

05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: Link