×

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.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)
Software:
GENREG
PDF BibTeX XML Cite
Full Text: Link