文章基本信息

标题：Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
本地全文：下载
作者：Argyrios Deligkas ; George B. Mertzios ; Paul G. Spirakis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：27:1-27:13
DOI：10.4230/LIPIcs.MFCS.2020.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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Î± (â^Sn+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.
关键词：Hamiltonian cycle; cubic graph; exact algorithm; approximation algorithm