{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:45Z","timestamp":1750220865265,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T00:00:00Z","timestamp":1575936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Recent trends in kernelization: theory and experimental evaluation"},{"name":"European Union under the European Regional Development Fund"},{"name":"Homing programme of the Foundation for Polish Science"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be sweeped with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm.<\/jats:p>\n          <jats:p>\n            In recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>t<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>t<\/jats:italic>\n              log\n              <jats:italic>t<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problems, namely, H\n            <jats:sc>AMILTONIAN<\/jats:sc>\n            C\n            <jats:sc>YCLE<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/3368631","type":"journal-article","created":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T13:21:36Z","timestamp":1575984096000},"page":"1-18","source":"Crossref","is-referenced-by-count":2,"title":["Finding Hamiltonian Cycle in Graphs of Bounded Treewidth"],"prefix":"10.1145","volume":"24","author":[{"given":"Micha\u0142","family":"Ziobro","sequence":"first","affiliation":[{"name":"Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. SageMath package. Retrieved from www.sagemath.org.  [n.d.]. SageMath package. Retrieved from www.sagemath.org."},{"key":"e_1_2_1_2_1","unstructured":"2018. Recent trends in kernelization: Theory and experimental evaluation\u2014project website. (2018). Retrieved from http:\/\/kernelization-experiments.mimuw.edu.pl.  2018. Recent trends in kernelization: Theory and experimental evaluation\u2014project website. (2018). Retrieved from http:\/\/kernelization-experiments.mimuw.edu.pl."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9185-7"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914)","author":"Bj\u00f6rklund Andreas","year":"2014","unstructured":"Andreas Bj\u00f6rklund , Petteri Kaski , Lukasz Kowalik , and Juho Lauri . 2014 . Engineering motif search for large graphs . In Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914) . SIAM, 104--118. Andreas Bj\u00f6rklund, Petteri Kaski, Lukasz Kowalik, and Juho Lauri. 2014. Engineering motif search for large graphs. In Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914). SIAM, 104--118."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 44--53","author":"Broersma Hajo","year":"2009","unstructured":"Hajo Broersma , Fedor V. Fomin , Pim van\u2019t Hof , and Dani\u00ebl Paulusma . 2009 . Fast exact algorithms for Hamiltonicity in claw-free graphs . In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 44--53 . Hajo Broersma, Fedor V. Fomin, Pim van\u2019t Hof, and Dani\u00ebl Paulusma. 2009. Fast exact algorithms for Hamiltonicity in claw-free graphs. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 44--53."},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_9_1","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3148227"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics","volume":"63","author":"Dell Holger","unstructured":"Holger Dell , Thore Husfeldt , Bart M. P. Jansen , Petteri Kaski , Christian Komusiewicz , and Frances A. Rosamond . 2017. The first parameterized algorithms and computational experiments challenge . In Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics , Vol. 63 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2017. The first parameterized algorithms and computational experiments challenge. In Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics, Vol. 63. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_13_1","volume-title":"The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. IPEC (2017","author":"Dell Holger","year":"2017","unstructured":"Holger Dell , Christian Komusiewicz , Nimrod Talmon , and Mathias Weller . 2017 . The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. IPEC (2017 ), 30:1--30:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30 Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. 2017. The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. IPEC (2017), 30:1--30:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9934-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21729"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0499-1"},{"key":"e_1_2_1_17_1","first-page":"98","article-title":"FHCP challenge set: The first set of structurally difficult instances of the Hamiltonian cycle problem","volume":"83","author":"Haythorpe Michael","year":"2018","unstructured":"Michael Haythorpe . 2018 . FHCP challenge set: The first set of structurally difficult instances of the Hamiltonian cycle problem . Bull. ICA 83 (2018), 98 -- 107 . Retrieved from http:\/\/arxiv.org\/abs\/1902.10352; challenge set at http:\/\/fhcp.edu.au\/fhcpcs. Michael Haythorpe. 2018. FHCP challenge set: The first set of structurally difficult instances of the Hamiltonian cycle problem. Bull. ICA 83 (2018), 98--107. Retrieved from http:\/\/arxiv.org\/abs\/1902.10352; challenge set at http:\/\/fhcp.edu.au\/fhcpcs.","journal-title":"Bull. ICA"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_2_1_19_1","first-page":"111","article-title":"Planar graphs, regular graphs, bipartite graphs, and Hamiltonicity","volume":"20","author":"Holton Derek A.","year":"1999","unstructured":"Derek A. Holton and Robert E. L. Aldred . 1999 . Planar graphs, regular graphs, bipartite graphs, and Hamiltonicity . Austral. J. Combin. 20 (1999), 111 -- 132 . Retrieved from http:\/\/ajc.maths.uq.edu.au\/pdf\/20\/ocr-ajc-v20-p111.pdf. Derek A. Holton and Robert E. L. Aldred. 1999. Planar graphs, regular graphs, bipartite graphs, and Hamiltonicity. Austral. J. Combin. 20 (1999), 111--132. Retrieved from http:\/\/ajc.maths.uq.edu.au\/pdf\/20\/ocr-ajc-v20-p111.pdf.","journal-title":"Austral. J. Combin."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1975.11993805"},{"key":"e_1_2_1_21_1","article-title":"Known algorithms on graphs of bounded treewidth are probably optimal","volume":"14","author":"Lokshtanov Daniel","year":"2018","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . 2018 . Known algorithms on graphs of bounded treewidth are probably optimal . ACM Trans. Algor. 14 , 2 (2018), 13:1--13:30. DOI:https:\/\/doi.org\/10.1145\/3170442 Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2018. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algor. 14, 2 (2018), 13:1--13:30. DOI:https:\/\/doi.org\/10.1145\/3170442","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010110"},{"key":"e_1_2_1_26_1","unstructured":"J. Statz. 2015. Unium. Retrieved from http:\/\/www.kittehface.com\/p\/unium.html.  J. Statz. 2015. Unium. Retrieved from http:\/\/www.kittehface.com\/p\/unium.html."},{"key":"e_1_2_1_27_1","volume-title":"Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR abs\/1709.08949","author":"Strasser Ben","year":"2017","unstructured":"Ben Strasser . 2017. Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR abs\/1709.08949 ( 2017 ). Retrieved from http:\/\/arxiv.org\/abs\/1709.08949. Ben Strasser. 2017. Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR abs\/1709.08949 (2017). Retrieved from http:\/\/arxiv.org\/abs\/1709.08949."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(69)80116-X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Micha\u0142 Ziobro and Marcin Pilipczuk. 2018. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. Code repository. Retrieved from https:\/\/github.com\/stalowyjez\/hc_tw_experiments.  Micha\u0142 Ziobro and Marcin Pilipczuk. 2018. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. Code repository. Retrieved from https:\/\/github.com\/stalowyjez\/hc_tw_experiments.","DOI":"10.1145\/3368631"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918)","volume":"103","author":"Ziobro Michal","year":"2018","unstructured":"Michal Ziobro and Marcin Pilipczuk . 2018 . Finding Hamiltonian cycle in graphs of bounded treewidth: Experimental evaluation . In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918) . LIPIcs, Gianlorenzo D\u2019Angelo (Ed.) , Vol. 103 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 29:1--29:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2018.29 Michal Ziobro and Marcin Pilipczuk. 2018. Finding Hamiltonian cycle in graphs of bounded treewidth: Experimental evaluation. In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918). LIPIcs, Gianlorenzo D\u2019Angelo (Ed.), Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 29:1--29:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2018.29"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368631","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:42Z","timestamp":1750202622000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368631"}},"subtitle":["Experimental Evaluation"],"short-title":[],"issued":{"date-parts":[[2019,12,10]]},"references-count":30,"alternative-id":["10.1145\/3368631"],"URL":"https:\/\/doi.org\/10.1145\/3368631","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,12,10]]}}}