{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T10:39:54Z","timestamp":1772793594498,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:00:00Z","timestamp":1718150400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:00:00Z","timestamp":1718150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P020372\/1"],"award-info":[{"award-number":["EP\/P020372\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,9]]},"abstract":"Abstract<\/jats:title>In this paper we consider the following problem: Given a Hamiltonian graph G<\/jats:italic>, and a Hamiltonian cycle C<\/jats:italic> of G<\/jats:italic>, can we compute a second Hamiltonian cycle $$C^{\\prime } \\ne C$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2260<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic>, and if yes, how quickly? If the input graph G<\/jats:italic> satisfies certain conditions (e.g.\u00a0if every vertex of G<\/jats:italic> is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating<\/jats:italic> the length of a second longest cycle on n<\/jats:italic>-vertex graphs with minimum degree $$\\delta $$<\/jats:tex-math>\n \u03b4<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and maximum degree $$\\Delta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We provide a linear-time algorithm for computing a cycle $$C^{\\prime } \\ne C$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2260<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of length at least $$n-4\\alpha (\\sqrt{n}+2\\alpha )+8$$<\/jats:tex-math>\n \n n<\/mml:mi>\n -<\/mml:mo>\n 4<\/mml:mn>\n \u03b1<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n +<\/mml:mo>\n 2<\/mml:mn>\n \u03b1<\/mml:mi>\n )<\/mml:mo>\n +<\/mml:mo>\n 8<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\alpha = \\frac{\\Delta -2}{\\delta -2}$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n =<\/mml:mo>\n \n \n \u0394<\/mml:mi>\n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n \n \u03b4<\/mml:mi>\n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This results provides a constructive proof of a recent result by Gir\u00e3o, Kittipassorn, and Narayanan in the regime of $$\\frac{\\Delta }{\\delta } = o(\\sqrt{n})$$<\/jats:tex-math>\n \n \n \u0394<\/mml:mi>\n \u03b4<\/mml:mi>\n <\/mml:mfrac>\n =<\/mml:mo>\n o<\/mml:mi>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability<\/jats:italic>, given that the input graph G<\/jats:italic> has a large enough minimum degree. More specifically, we prove that for every $$0<p\\le 0.02$$<\/jats:tex-math>\n \n 0<\/mml:mn>\n <<\/mml:mo>\n p<\/mml:mi>\n \u2264<\/mml:mo>\n 0.02<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, if the minimum degree of G<\/jats:italic> is at least $$\\frac{8}{p} \\log \\sqrt{8}n + 4$$<\/jats:tex-math>\n \n \n 8<\/mml:mn>\n p<\/mml:mi>\n <\/mml:mfrac>\n log<\/mml:mo>\n \n 8<\/mml:mn>\n <\/mml:msqrt>\n n<\/mml:mi>\n +<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, then a second Hamiltonian cycle can be computed with probability at least $$1 - \\frac{1}{n}\\left( \\frac{50}{p^4} + 1 \\right) $$<\/jats:tex-math>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \n 1<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mfrac>\n \n \n 50<\/mml:mn>\n \n p<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n <\/mml:mfrac>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in $$poly(n) \\cdot 2^{4pn}$$<\/jats:tex-math>\n \n p<\/mml:mi>\n o<\/mml:mi>\n l<\/mml:mi>\n y<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n 2<\/mml:mn>\n \n 4<\/mml:mn>\n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. This result implies that, when the minimum degree $$\\delta $$<\/jats:tex-math>\n \u03b4<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when $$\\delta = \\omega (\\log n)$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n =<\/mml:mo>\n \u03c9<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, our probabilistic algorithm works in $$2^{o(n)}$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n \n o<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time.<\/jats:p>","DOI":"10.1007\/s00453-024-01238-z","type":"journal-article","created":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T19:01:36Z","timestamp":1718218896000},"page":"2766-2785","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle"],"prefix":"10.1007","volume":"86","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7182-585X","authenticated-orcid":false,"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,12]]},"reference":[{"key":"1238_CR1","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00373-006-0666-z","volume":"22","author":"S Abbasi","year":"2006","unstructured":"Abbasi, S., Jamshed, A.: A degree constraint for uniquely Hamiltonian graphs. Graphs Comb. 22, 433\u2013442 (2006)","journal-title":"Graphs Comb."},{"issue":"1","key":"1238_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1006\/jagm.1998.0998","volume":"31","author":"C Bazgan","year":"1999","unstructured":"Bazgan, C., Santha, M., Tuza, Z.: On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs. J. Algorithms 31(1), 249\u2013268 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"1238_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"issue":"1","key":"1238_CR4","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/110839229","volume":"43","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. SIAM J. Comput. 43(1), 280\u2013299 (2014)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1238_CR5","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/2151171.2151181","volume":"8","author":"A Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms 8(2), 18:1-18:13 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"1238_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"1238_CR7","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"2","key":"1238_CR8","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/jctb.1998.1845","volume":"74","author":"JA Bondy","year":"1998","unstructured":"Bondy, J.A., Jackson, B.: Vertices of small degree in uniquely Hamiltonian graphs. J. Comb. Theory Ser. B 74(2), 265\u2013275 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1238_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0012-365X(00)00260-0","volume":"235","author":"K Cameron","year":"2001","unstructured":"Cameron, K.: Thomason\u2019s algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk\u2019s graphs. Discrete Math. 235, 69\u201377 (2001)","journal-title":"Discrete Math."},{"key":"1238_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast hamiltonicity checking via bases of perfect matchings. In: Proceedings of the 45th ACM Symposium on Theory of Computing Conference (STOC), pp. 301\u2013310 (2013)","DOI":"10.1145\/2488608.2488646"},{"issue":"3","key":"1238_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3148227","volume":"65","author":"M Cygan","year":"2018","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast hamiltonicity checking via bases of perfect matchings. J. ACM (JACM) 65(3), 1\u201346 (2018)","journal-title":"J. ACM (JACM)"},{"key":"1238_CR12","unstructured":"Deligkas, A., Mertzios, G.B., Spirakis, P.G., Zamaraev, V.: Exact and approximate algorithms for computing a second Hamiltonian cycle. In: Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), vol. 170, pp. 27:1\u201327:13 (2020)"},{"issue":"3","key":"1238_CR13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0095-8956(80)90087-8","volume":"29","author":"RC Entringer","year":"1980","unstructured":"Entringer, R.C., Swart, H.: Spanning cycles of nearly cubic graphs. J. Comb. Theory Ser. B 29(3), 303\u2013309 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1238_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.7155\/jgaa.00137","volume":"11","author":"D Eppstein","year":"2007","unstructured":"Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61\u201381 (2007)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"1238_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/jgt.21729","volume":"75","author":"H Fleischner","year":"2014","unstructured":"Fleischner, H.: Uniquely Hamiltonian graphs of minimum degree 4. J. Graph Theory 75(2), 167\u2013177 (2014)","journal-title":"J. Graph Theory"},{"issue":"1","key":"1238_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s11856-018-1798-6","volume":"229","author":"A Gir\u00e3o","year":"2019","unstructured":"Gir\u00e3o, A., Kittipassorn, T., Narayanan, B.: Long cycles in Hamiltonian graphs. Isr. J. Math. 229(1), 269\u2013285 (2019)","journal-title":"Isr. J. Math."},{"issue":"3","key":"1238_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/jgt.20205","volume":"54","author":"P Haxell","year":"2007","unstructured":"Haxell, P., Seamone, B., Verstraete, J.: Independent dominating sets and Hamiltonian cycles. J. Graph Theory 54(3), 233\u2013244 (2007)","journal-title":"J. Graph Theory"},{"issue":"1","key":"1238_CR18","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"1238_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jda.2014.02.001","volume":"27","author":"M Li\u015bkiewicz","year":"2014","unstructured":"Li\u015bkiewicz, M., Schuster, M.R.: A new upper bound for the traveling salesman problem in cubic graphs. J. Discrete Algorithms 27, 1\u201320 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"1238_CR20","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"1238_CR21","unstructured":"Sheehan, J.: The multiplicity of Hamiltonian circuits in a graph. In: Recent Advances in Graph Theory, pp. 477\u2013480 (1975)"},{"key":"1238_CR22","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/S0167-5060(08)70511-9","volume":"3","author":"AG Thomason","year":"1978","unstructured":"Thomason, A.G.: Hamiltonian cycles and uniquely edge colourable graphs. Ann. Discrete Math. 3, 259\u2013268 (1978)","journal-title":"Ann. Discrete Math."},{"key":"1238_CR23","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/S0167-5060(08)70511-9","volume":"3","author":"AG Thomason","year":"1978","unstructured":"Thomason, A.G.: Hamiltonian cycles and uniquely edge colourable graphs. Adv. Graph Theory 3, 259\u2013268 (1978)","journal-title":"Adv. Graph Theory"},{"issue":"2","key":"1238_CR24","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1006\/jctb.1997.1776","volume":"71","author":"C Thomassen","year":"1997","unstructured":"Thomassen, C.: Chords of longest cycles in cubic graphs. J. Comb. Theory Ser. B 71(2), 211\u2013214 (1997)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1238_CR25","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jctb.1997.1794","volume":"72","author":"C Thomassen","year":"1998","unstructured":"Thomassen, C.: Independent dominating sets and a second Hamiltonian cycle in regular graphs. J. Comb. Theory Ser. B 72(1), 104\u2013109 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"1238_CR26","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","volume":"1","author":"WT Tutte","year":"1946","unstructured":"Tutte, W.T.: On Hamiltonian circuits. J. Lond. Math. Soc. 1(2), 98\u2013101 (1946)","journal-title":"J. Lond. Math. Soc."},{"key":"1238_CR27","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"},{"issue":"2","key":"1238_CR28","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s00453-015-9970-4","volume":"74","author":"M Xiao","year":"2016","unstructured":"Xiao, M., Nagamochi, H.: An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. Algorithmica 74(2), 713\u2013741 (2016)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01238-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01238-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01238-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:05:33Z","timestamp":1725433533000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01238-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,12]]},"references-count":28,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1238"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01238-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,12]]},"assertion":[{"value":"18 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}