2020/04/13 by Argyrios Deligkas, George B. Mertzios, Deligkas, Argyrios +5
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2004.06036
openalex publication_date 2020/04/13 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In this paper we consider the following total functional problem: Given a\ncubic Hamiltonian graph G and a Hamiltonian cycle C0 of G, how can we\ncompute a second Hamiltonian cycle C1 \≠ C0 of G? Cedric Smith proved\nin 1946, using a non-constructive parity argument, that such a second\nHamiltonian cycle always exists. Our main result is an algorithm which computes\nthe second Hamiltonian cycle in time O(n \⋅ 2(0.3-\ε)n) time,\nfor some positive constant \ε>0, and in polynomial space, thus\nimproving the state of the art running time for solving this problem. Our\nalgorithm is based on a fundamental structural property of Thomason's lollipop\nalgorithm, which we prove here for the first time. In the direction of\napproximating the length of a second cycle in a Hamiltonian graph G with a\ngiven Hamiltonian cycle C0 (where we may not have guarantees on the\nexistence of a second Hamiltonian cycle), we provide a linear-time algorithm\ncomputing a second cycle with length at least n - 4\α\n(\√(n)+2\α)+8, where \α = \(\Δ-2)/(\δ-2) and\n\δ,\Δ are the minimum and the maximum degree of the graph,\nrespectively. This approximation result also improves the state of the art.\n