Computing second Hamiltonian cycles

14^th October 2020, 13:00
Paul Spirakis

Abstract

In this work we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C0 of G, how can we compute a second Hamiltonian cycle C1 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.2998n)) time and in linear space, thus improving the state of the art running time of O(2^(0.3n)) for solving this problem (among deterministic algorithms running in polynomial space). 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 C0 (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle of length n-4a(root(n)+2a)+8 where a=(D-2)/(d-2) and D,d are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

Authors: Argyrios Deligkas , George Mertzios, Paul Spirakis and Viktor Zamaraev.
Appeared in MFCS 2020