Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle



Deligkas, Argyrios, Mertzios, George B, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2020) Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. Leibniz International Proceedings in Informatics, LIPIcs, 170.

[img] Text
2004.06036v1.pdf - Submitted version

Download (586kB) | Preview

Abstract

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 \neq 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 \cdot 2^{(0.3-\varepsilon)n})$ time, for some positive constant $\varepsilon>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\alpha (\sqrt{n}+2\alpha)+8$, where $\alpha = \frac{\Delta-2}{\delta-2}$ and $\delta,\Delta$ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

Item Type: Article
Additional Information: 28 pages, 4 algorithms, 5 figures
Uncontrolled Keywords: cs.DS, cs.DS, cs.CC, G.2.2; F.2.2; G.2.1
Depositing User: Symplectic Admin
Date Deposited: 24 Apr 2020 14:51
Last Modified: 18 Jan 2023 23:54
DOI: 10.4230/LIPIcs.MFCS.2020.27
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3084303