Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle

Abstract In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C^ C C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e. g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n -vertex graphs with minimum degree δ and maximum degree Δ. We provide a linear-time algorithm for computing a cycle C^ C C ′ ≠ C of length at least n-4 (n+2) +8 n - 4 α (n + 2 α) + 8, where = -2 -2 α = Δ - 2 δ - 2. This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of = o (n) Δ δ = o (n). Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0 0 p ≤ 0. 02, if the minimum degree of G is at least 8p 8n + 4 8 p log 8 n + 4, then a second Hamiltonian cycle can be computed with probability at least 1 - 1n (50p⁴ + 1) 1 - 1 n 50 p 4 + 1 in poly (n) 2^4pn p o l y (n) · 2 4 p n time. This result implies that, when the minimum degree δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when = (n) δ = ω (log n), our probabilistic algorithm works in 2^o (n) 2 o (n) time.