Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle

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<p≤ 0.02 0 < p ≤ 0.02 , if the minimum degree of G is at least 8/p log √8n + 4 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least 1 - 1/n( 50/p⁴ + 1 ) 1 - 1 n 50 p 4 + 1 in poly(n) · 2⁴ᵖⁿ 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 δ = ω (log n) δ = ω ( log n ) , our probabilistic algorithm works in 2ᵒ⁽ⁿ⁾ 2 o ( n ) time.