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