Deligkas, Argyrios ;
Mertzios, George B. ;
Spirakis, Paul G. ;
Zamaraev, Viktor
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
Abstract
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 nonconstructive 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 lineartime 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.
BibTeX  Entry
@InProceedings{deligkas_et_al:LIPIcs:2020:12695,
author = {Argyrios Deligkas and George B. Mertzios and Paul G. Spirakis and Viktor Zamaraev},
title = {{Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {27:127:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12695},
URN = {urn:nbn:de:0030drops126953},
doi = {10.4230/LIPIcs.MFCS.2020.27},
annote = {Keywords: Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm}
}
18.08.2020
Keywords: 

Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 