A linear-size conversion of HCP to 3HCP. (English) Zbl 1321.05144

Ejov, V.; Haythorpe, M.; Rossomakhine, S.

Australas. J. Comb. 62, Part 1, 45-58 (2015).

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.

MSC:

05C45	Eulerian and Hamiltonian graphs
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

Hamiltonian cycle problem; sub-quartic graph

Software:

GENREG