Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle

Deligkas, Argyrios; Mertzios, George B.; Spirakis, Paul G.; Zamaraev, Viktor

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 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 of length at least n-4α(n+2α)+8, where α=Δ-2δ-2. This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of Δδ=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

Citation

Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2024). Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle. Algorithmica, 86(9), 2766-2785. https://doi.org/10.1007/s00453-024-01238-z

• Journal Article Type: Article
• Acceptance Date: Apr 24, 2024
• Online Publication Date: Jun 12, 2024
• Publication Date: Sep 1, 2024
• Deposit Date: Nov 6, 2023
• Publicly Available Date: Jun 19, 2024
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 86
• Issue: 9
• Pages: 2766-2785
• DOI: https://doi.org/10.1007/s00453-024-01238-z
• Keywords: Approximation algorithm, Graph with minimum degree 3, Randomized algorithm, Hamiltonian cycle
• Public URL: https://durham-repository.worktribe.com/output/1897832