 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-126953
URL:

; ; ;

### Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

 pdf-format:

### 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 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.

### 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:1--27:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-159-7},
ISSN =	{1868-8969},
year =	{2020},
volume =	{170},
editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 