2026-07-23T03:45:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12695 2024-03-06T10:50:36Z ddc:004 open_access

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle Deligkas, Argyrios Mertzios, George B. Spirakis, Paul G. Zamaraev, Viktor Hamiltonian cycle cubic graph exact algorithm approximation algorithm In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C₀ of G, how can we compute a second Hamiltonian cycle C₁ ≠ C₀ of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(n⋅2^0.299862744n) = O(1.23103ⁿ) time and in linear space, thus improving the state of the art running time of O*(2^0.3n) = O(1.2312ⁿ) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle C₆ on 6 vertices, the running time becomes O(n⋅ 2^0.2971925n) = O(1.22876ⁿ). Our algorithm is based on a fundamental structural property of Thomason’s lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle C₀ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least n - 4α (√n+2α)+8, where α = (Δ-2)/(δ-2) and δ,Δ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Argyrios Deligkas and George B. Mertzios and Paul G. Spirakis and Viktor Zamaraev 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.27 urn:nbn:de:0030-drops-126953 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.27 eng https://creativecommons.org/licenses/by/3.0/legalcode