License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.27
URN: urn:nbn:de:0030-drops-126953
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12695/
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 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},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12695},
URN = {urn:nbn:de:0030-drops-126953},
doi = {10.4230/LIPIcs.MFCS.2020.27},
annote = {Keywords: Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm}
}
|
Keywords: |
|
Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
