A Linear-size Conversion of HCP to 3HCP

Vladimir Ejov, Michael Haythorpe, Serguei Rossomakhine

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)

    Abstract

    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 Karp in 1972. 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.

    Original languageEnglish
    Pages (from-to)45-58
    Number of pages14
    JournalAustralasian Journal of Combinatorics, the
    Volume62
    Issue number1
    Publication statusPublished - Jun 2015

    Fingerprint Dive into the research topics of 'A Linear-size Conversion of HCP to 3HCP'. Together they form a unique fingerprint.

    Cite this