{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:31Z","timestamp":1781077711170,"version":"3.54.1"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            For the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give\n            <jats:italic>c<\/jats:italic>\n            <jats:bold>\n              <jats:sup>tw<\/jats:sup>\n            <\/jats:bold>\n            |\n            <jats:italic>V<\/jats:italic>\n            |\n            <jats:sup>O(1)<\/jats:sup>\n            time algorithms, where\n            <jats:bold>tw<\/jats:bold>\n            is the treewidth of the input graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V,E<\/jats:italic>\n            ) and\n            <jats:italic>c<\/jats:italic>\n            is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best\u2013known algorithms were naive dynamic programming schemes running in at least\n            <jats:bold>tw<\/jats:bold>\n            <jats:sup>\n              <jats:bold>tw<\/jats:bold>\n            <\/jats:sup>\n            time.\n          <\/jats:p>\n          <jats:p>\n            We bridge this gap by introducing a technique we named Cut&amp;Count that allows to produce\n            <jats:italic>c<\/jats:italic>\n            <jats:bold>\n              <jats:sup>tw<\/jats:sup>\n            <\/jats:bold>\n            |\n            <jats:italic>V<\/jats:italic>\n            |\n            <jats:sup>O(1)<\/jats:sup>\n            time Monte-Carlo algorithms for most connectivity-type problems, including\n            <jats:sc>Hamiltonian Path<\/jats:sc>\n            ,\n            <jats:sc>Steiner Tree<\/jats:sc>\n            ,\n            <jats:sc>Feedback Vertex Set<\/jats:sc>\n            and\n            <jats:sc>Connected Dominating Set<\/jats:sc>\n            . These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and\n            <jats:italic>H<\/jats:italic>\n            -minor-free graphs and exact algorithms on graphs of bounded degree. The constant\n            <jats:italic>c<\/jats:italic>\n            in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least\n            <jats:bold>tw<\/jats:bold>\n            <jats:sup>\n              <jats:bold>tw<\/jats:bold>\n            <\/jats:sup>\n            equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA\u201911].\n          <\/jats:p>\n          <jats:p>\n            In contrast to the problems aimed at\n            <jats:italic>minimizing<\/jats:italic>\n            the number of connected components that we solve using Cut&amp;Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be bridged for some problems that aim to\n            <jats:italic>maximize<\/jats:italic>\n            the number of connected components like\n            <jats:sc>Cycle Packing<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/3506707","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T11:32:35Z","timestamp":1646393555000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2472-2975","authenticated-orcid":false,"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9149-4162","authenticated-orcid":false,"given":"Johan M. M.","family":"Van Rooij","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[{"name":"Google Inc., Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0116-5"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_23"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622248.1622256"},{"key":"e_1_3_2_6_2","volume-title":"Matrix Decompositions and Algorithmic Applications to (Hyper)Graphs","author":"Bergougnoux Benjamin","year":"2019","unstructured":"Benjamin Bergougnoux. 2019. Matrix Decompositions and Algorithmic Applications to (Hyper)Graphs. Ph.D. Dissertation. Universit\u00e9 Clermont Auvergne."},{"key":"e_1_3_2_7_2","unstructured":"Benjamin Bergougnoux and Mamadou Moustapha Kant\u00e9. 2017. Fast exact algorithms for some connectivity problems parameterized by clique-width. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916) Vol. 63 Jiong Guo and Danny Hermelin (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_8_2","first-page":"17:1\u201317:14","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms, ESA 201 (Leibniz International Proceedings in Informatics)","volume":"144","author":"Bergougnoux Benjamin","year":"2019","unstructured":"Benjamin Bergougnoux and Mamadou Moustapha Kant\u00e9. 2019. More applications of the d-neighbor equivalence: Connectivity and acyclicity constraints. In Proceedings of the 27th Annual European Symposium on Algorithms, ESA 201 (Leibniz International Proceedings in Informatics). M. A. Bender, O. Svensson, and G. Herman (Eds.), Vol. 144, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:14."},{"key":"e_1_3_2_9_2","volume-title":"Amortized Analysis of Exponential Time and Parameterized Algorithms: Measure and Conquer and Reference Search Trees","author":"Binkele-Raible Daniel","year":"2010","unstructured":"Daniel Binkele-Raible. 2010. Amortized Analysis of Exponential Time and Parameterized Algorithms: Measure and Conquer and Reference Search Trees. Ph.D. Dissertation. University of Trier, Trier, Germany."},{"key":"e_1_3_2_10_2","volume-title":"Private communication","author":"Bj\u00f6rklund Andreas","year":"2011","unstructured":"Andreas Bj\u00f6rklund. 2011. Private communication. (2011)."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Andreas Bj\u00f6rklund Thore Husfeldt Petteri Kaski and Mikko Koivisto. 2017. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. 87 (2010) 119\u2013139.","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151181"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054194000049"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_3_2_19_2","first-page":"8:1\u20138:23","volume-title":"Proceedings of the 11th International Symposium on Parameterized and Exact Computation.","author":"Borradaile Glencora","unstructured":"Glencora Borradaile and Hung Le. Optimal dynamic program for r-domination problems over tree decompositions. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation.8:1\u20138:23."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9460-7"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9904-6"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_3_2_24_2","first-page":"1080","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Curticapean Radu","year":"2018","unstructured":"Radu Curticapean, Nathan Lindzey, and Jesper Nederlof. 2018. A tight lower bound for counting hamiltonian cycles via matrix rank. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. A. Czumaj (Ed.). Society for Industrial and Applied Mathematics, 1080\u20131099."},{"key":"e_1_3_2_25_2","volume-title":"Cut&Count Technique for Graph Connectivity Problems Parameterized by Treewidth","author":"Cygan Marek","year":"2012","unstructured":"Marek Cygan. 2012. Cut&Count Technique for Graph Connectivity Problems Parameterized by Treewidth. Ph.D. Dissertation. University of Warsaw, Warsaw, Poland."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_9"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.36"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488646"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"Marek Cygan Jesper Nederlof Marcin Pilipczuk Micha\u0142 Pilipczuk Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk. 2011. Solving connectivity problems parameterized by treewidth in single exponential time. arXiv:1103.0534. Retrieved from https:\/\/arxiv.org\/abs\/1103.0534.","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.018"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_18"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.02.004"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9296-1"},{"key":"e_1_3_2_39_2","first-page":"191","volume-title":"Proceedings of the Complexity Theory: Current Research","author":"Downey Rodney G.","year":"1993","unstructured":"Rodney G. Downey and Michael R. Fellows. 1993. Fixed parameter tractability and completeness. In Proceedings of the Complexity Theory: Current Research. K. Ambos-Spies, S. Homer, and U. Sch\u00f6ning (Eds.), Cambridge University Press, 191\u2013225."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00137"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9133-3"},{"key":"e_1_3_2_44_2","first-page":"142","volume-title":"25st Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Fomin Fedor V.","year":"2014","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. 2014. Efficient computation of representative sets with applications in parameterized and exact algorithms. In 25st Annual ACM-SIAM Symposium on Discrete Algorithms. C. Chekuri (Ed.), Society for Industrial and Applied Mathematics, 142\u2013151."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_6"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.37236\/619"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.038"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_3_2_49_2","first-page":"29:1\u201329:16","volume-title":"Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science","volume":"154","author":"Hegerfeld Falko","year":"2020","unstructured":"Falko Hegerfeld and Stefan Kratsch. 2020. 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. C. Paul and M. Bl\u00e4ser (Eds.), Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 29:1\u201329:16."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1287\/educ.1053.0017"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73545-8_13"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28639-4_21"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_58_2","volume-title":"Treewidth, Computations and Approximations","author":"Kloks Ton","year":"1994","unstructured":"Ton Kloks. 1994. Treewidth, Computations and Approximations. Springer."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.58"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.61"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.60"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9394-2"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9089-3"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"issue":"3","key":"e_1_3_2_67_2","first-page":"685","article-title":"Inclusion\/Exclusion meets measure and conquer","volume":"69","author":"Nederlof Jesper","year":"2014","unstructured":"Jesper Nederlof, Johan M. M. van Rooij, and Thomas C. van Dijk. 2014. Inclusion\/Exclusion meets measure and conquer. Algorithmica 69, 3 (2014), 685\u2013740.","journal-title":"Algorithmica"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_3_2_69_2","first-page":"27:1\u201327:12","volume-title":"Proceedings of the11th International Symposium on Parameterized and Exact Computation","volume":"63","author":"Pino Willem J. A.","year":"2017","unstructured":"Willem J. A. Pino, Hans L. Bodlaender, and Johan M. M. van Rooij. 2017. Cut and count and representative sets on branch decompositions. In Proceedings of the11th International Symposium on Parameterized and Exact Computation. Jiong Guo and Danny Hermelin (Eds.), Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 27:1\u201327:12."},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2005.05.037"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90042-9"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.5555\/1093468.1712339"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"e_1_3_2_79_2","first-page":"435","volume-title":"Proceedings of the16th International Computer Science Symposium in Russia","volume":"12730","author":"Rooij Johan M. M. van","year":"2021","unstructured":"Johan M. M. van Rooij. 2021. A generic convolution algorithm for join operations on tree decompositions. In Proceedings of the16th International Computer Science Symposium in Russia. Rahul Santhanam and Daniil Musatov (Eds.), Vol. 12730. Springer, 435\u2013459."},{"key":"e_1_3_2_80_2","first-page":"566","volume-title":"Proceedings of the 17th Annual European Symposium on Algorithms","volume":"5757","author":"Rooij Johan M. M. van","year":"2009","unstructured":"Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. 2009. Dynamic programming on tree decompositions using generalised fast subset convolution. In Proceedings of the 17th Annual European Symposium on Algorithms. A. Fiat and P. Sanders (Eds.), Vol. 5757. Springer, 566\u2013577."},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3506707","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3506707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:50Z","timestamp":1750191110000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3506707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":80,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3506707"],"URL":"https:\/\/doi.org\/10.1145\/3506707","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}