{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:51Z","timestamp":1787322891403,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["850979"],"award-info":[{"award-number":["850979"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["853234"],"award-info":[{"award-number":["853234"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["948057"],"award-info":[{"award-number":["948057"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["613.009.031b"],"award-info":[{"award-number":["613.009.031b"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For many algorithmic problems on graphs of treewidth [Formula: see text], a standard dynamic programming approach gives algorithms with time and space complexity [Formula: see text]. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form [Formula: see text], where [Formula: see text] is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity [Formula: see text] on graphs of treewidth [Formula: see text], but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut&amp;Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity [Formula: see text]. Recently, Hegerfeld and Kratsch (STACS\u201920) showed that, for some of those problems, the Cut&amp;Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time [Formula: see text] and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit [Formula: see text]-time and polynomial space algorithms on graphs of treedepth [Formula: see text]. The algorithms are randomized Monte Carlo with only false negatives.<\/jats:p>","DOI":"10.1137\/22m1518943","type":"journal-article","created":{"date-parts":[[2023,7,25]],"date-time":"2023-07-25T11:38:31Z","timestamp":1690285111000},"page":"1566-1586","source":"Crossref","is-referenced-by-count":3,"title":["Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space"],"prefix":"10.1137","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":true,"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[{"name":"Utrecht University, Utrecht, 3584 CC, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, 02-097, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9654-8094","authenticated-orcid":true,"given":"Celine M. F.","family":"Swennenhuis","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, 5600 MB, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karol","family":"W\u0119grzycki","sequence":"additional","affiliation":[{"name":"Saarland University and Max Planck Institute for Informatics, Saarbr\u00fccken, 66123, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"ref1","unstructured":"M. Belbasi  and \nM. F\u00fcrer , Saving Space by Dynamic Algebraization Based on Tree Decomposition: Minimum Dominating Set, preprint, https:\/\/arxiv.org\/abs\/1711.10088, 2017."},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"M. Belbasi  and \nM. F\u00fcrer , A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization, in Proceedings of the 14th International Computer Science Symposium in Russia, CSR 2019, Lecture Notes in Comput. Sci. 11532, Springer, 2019, pp. 38\u201349.","DOI":"10.1007\/978-3-030-19955-5_4"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.02.030"},{"key":"ref4","unstructured":"B. Bergougnoux  and \nM. M. Kant\u00e9 , More applications of the d-neighbor equivalence: Connectivity and acyclicity constraints, in Proceedings of the 27th Annual European Symposium on Algorithms, ESA 2019, LIPIcs. Leibniz Int. Proc. Inform. 144, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, 17."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3148227"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3506707"},{"key":"ref10","unstructured":"W. Czerwi\u0144ski , \nW. Nadara , and \nM. Pilipczuk , Improved bounds for the excluded-minor approximation of treedepth, in Proceedings of the 27th Annual European Symposium on Algorithms, ESA 2019, LIPIcs. Leibniz Int. Proc. Inform. 144, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019 34."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103186"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref14","unstructured":"A. Drucker , \nJ. Nederlof , and \nR. Santhanam , Exponential time paradigms through the polynomial time lens, in Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, LIPIcs. Leibniz Int. Proc. Inform. 57, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, 2016, 36."},{"key":"ref15","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"Flum J.","year":"2006"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9751-3"},{"key":"ref18","first-page":"7","volume":"15","author":"Ganian R.","year":"2019","journal-title":"Log. Methods Comput. Sci."},{"key":"ref19","unstructured":"F. Hegerfeld  and \nS. Kratsch , Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space, in Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, LIPIcs. Leibniz Int. Proc. Inform. 154, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, 29."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00614-4"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"T. Korhonen , A single-exponential time 2-approximation algorithm for treewidth, in Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, IEEE, 2021, pp. 84\u2013192.","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov , \nM. Mnich , and \nS. Saurabh , Planar   \\(k\\)  -path in subexponential time and polynomial space, in Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, Lecture Notes in Comput. Sci. 6986, Springer, 2011, pp. 262\u2013270.","DOI":"10.1007\/978-3-642-25870-1_24"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov  and \nJ. Nederlof , Saving space by algebraization, in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, ACM, 2010, pp. 321\u2013330.","DOI":"10.1145\/1806689.1806735"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"ref25","unstructured":"W. Nadara , \nM. Pilipczuk , and \nM. Smulewicz , Computing treedepth in polynomial space and linear FPT time, in Proceedings of the 30th Annual European Symposium on Algorithms, ESA 2022, LIPIcs. Leibniz Int. Proc. Inform. 244, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, 79."},{"key":"ref26","unstructured":"J. Nederlof . Inclusion Exclusion for Hard Problems, Master\u2019s thesis, Utrecht University, Utrecht, The Netherlands, 2008."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"J. Nederlof , \nM. Pilipczuk , \nC. M. F. Swennenhuis , and \nK. W\u0119grzycki , Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space, in Proceedings on the 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG, 2020, Leeds, UK, 2020, Lecture Notes in Comput. Sci. 12301, Springer, Cham, 2020, pp. 27\u201339.","DOI":"10.1007\/978-3-030-60440-0_3"},{"key":"ref28","unstructured":"J. Nederlof , \nM. Pilipczuk , \nC. M. F. Swennenhuis , and \nK. W\u0119grzycki , Isolation schemes for problems on decomposable graphs, in Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, LIPIcs. Leibniz Int. Proc. Inform. 219, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, 50."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"M. Pilipczuk  and \nS. Siebertz , Polynomial bounds for centered colorings on proper minor-closed graph classes, in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, SIAM, 2019, pp. 1501\u20131520, https:\/\/doi.org\/10.1137\/1.9781611975482.91.","DOI":"10.1137\/1.9781611975482.91"},{"key":"ref31","first-page":"18","volume":"9","author":"Pilipczuk M.","year":"2018","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref32","unstructured":"W. J. A. Pino , \nH. L. Bodlaender , and \nJ. M. M. van Rooij , Cut and Count and representative sets on branch decompositions, in Proceedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, LIPIcs. Leibniz Int. Proc. Inform. 63, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, 27."},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"F. Reidl , \nP. Rossmanith , \nF. S\u00e1nchez Villaamil , and \nS. Sikdar , A faster parameterized algorithm for treedepth, in Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Lecture Notes in Comput. Sci. 8572, Springer, 2014, pp. 931\u2013942.","DOI":"10.1007\/978-3-662-43948-7_77"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0489-3"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1518943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:31:54Z","timestamp":1787319114000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1518943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1137\/22M1518943"],"URL":"https:\/\/doi.org\/10.1137\/22m1518943","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,24]]}}}