Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

04/13/2020
by   Argyrios Deligkas, et al.
0

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C_0 of G, how can we compute a second Hamiltonian cycle C_1 ≠ C_0 of G? Cedric Smith proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is an algorithm which computes the second Hamiltonian cycle in time O(n · 2^(0.3-ε)n) time, for some positive constant ε>0, and in polynomial space, thus improving the state of the art running time for solving this problem. 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 Hamiltonian graph G with a given Hamiltonian cycle C_0 (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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset