{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:25:17Z","timestamp":1753885517125,"version":"3.41.2"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"abstract":"\n Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition\u2019s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here,\n treedepth<\/jats:italic>\n is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone.\n <\/jats:p>\n \n Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on\n n<\/jats:italic>\n -vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth\n d<\/jats:italic>\n and using\n k<\/jats:italic>\n labels,\n \n \n \u2022<\/jats:label>\n \n Independent Set<\/jats:sc>\n and\n Dominating Set<\/jats:sc>\n can be solved in time\n \n \\(2^{\\mathcal {O}(dk)}\\cdot n^{\\mathcal {O}(1)} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n using\n \n \\(\\mathcal {O}(dk\\log n) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space;\n <\/jats:p>\n <\/jats:list-item>\n \n \u2022<\/jats:label>\n \n Max Cut<\/jats:sc>\n can be solved in time\n \n \\(n^{\\mathcal {O}(dk)} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n using\n \n \\(\\mathcal {O}(dk\\log n) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n We also establish a lower bound, conditional on a certain assumption about the complexity of\n Longest Common Subsequence<\/jats:sc>\n , which shows that at least in the case of\n Independent Set<\/jats:sc>\n the exponent of the parametric factor in the time complexity has to grow with\n d<\/jats:italic>\n if one wishes to keep the space complexity polynomial..\n <\/jats:p>","DOI":"10.1145\/3723880","type":"journal-article","created":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T10:29:01Z","timestamp":1742293741000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6270-3663","authenticated-orcid":false,"given":"Benjamin","family":"Bergougnoux","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"},{"name":"Aix-Marseille Universit\u00e9, CNRS, LIS, Marseille France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6165-1566","authenticated-orcid":false,"given":"Vera","family":"Chekan","sequence":"additional","affiliation":[{"name":"Humboldt-Universitat zu Berlin, Berlin Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":false,"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Wien Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1838-7744","authenticated-orcid":false,"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Clermont Auvergne, Clermont Auvergne INP, CNRS, Clermont-Ferrand France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4721-5354","authenticated-orcid":false,"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[{"name":"Hamburg University of Technology, Hamburg Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6889-7286","authenticated-orcid":false,"given":"Sang-il","family":"Oum","sequence":"additional","affiliation":[{"name":"Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon Korea (the Republic of)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7891-1988","authenticated-orcid":false,"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5240-7257","authenticated-orcid":false,"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a012"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBE.2007.4375584"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.03.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2023.18"},{"key":"e_1_2_1_7_1","volume-title":"Proc. STOC","author":"Bj\u00f6rklund Andreas","year":"2007","unstructured":"Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2007. Fourier meets M\u00f6bius: fast subset convolution. In Proc. STOC 2007. 67\u201374."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00251-D"},{"key":"e_1_2_1_9_1","volume-title":"Proc. Inform., Vol.\u00a0 249)","author":"Bodlaender L.","year":"2022","unstructured":"Hans\u00a0L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma\u00a0T. Lima. 2022. XNLP-completeness for parameterized problems on graphs with a linear structure. In 17th International Symposium on Parameterized and Exact Computation(LIPIcs. Leibniz Int. Proc. Inform., Vol.\u00a0 249). Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Paper No. 8, 18. doi: 10.4230\/lipics.ipec.2022.8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2022.6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00027"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/lipics.icalp.2023.27"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.03.004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_15_1","unstructured":"Marek Cygan, Fedor\u00a0V 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_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3506707"},{"key":"e_1_2_1_17_1","volume-title":"Branch-depth: Generalizing tree-depth of graphs. European J. Combin. 90(2020), Article 103186.","author":"DeVos Matt","year":"2020","unstructured":"Matt DeVos, O-joung Kwon, and Sang-il Oum. 2020. Branch-depth: Generalizing tree-depth of graphs. European J. Combin. 90(2020), Article 103186."},{"volume-title":"Vol.\u00a0 173","author":"Diestel Reinhard","key":"e_1_2_1_18_1","unstructured":"Reinhard Diestel. 2012. Graph Theory (4thed.). Graduate texts in mathematics, Vol.\u00a0 173. Springer."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-19(2:14)2023"},{"key":"e_1_2_1_21_1","volume-title":"Proc. LICS","author":"Dreier Jan","year":"2022","unstructured":"Jan Dreier, Jakub Gajarsk\u00fd, Sandra Kiefer, Micha\u0142 Pilipczuk, and Szymon Toru\u0144czyk. 2022. Treelike Decompositions for Transductions of Sparse Graphs. In Proc. LICS 2022. 31:1\u201331:14. doi: 10.1145\/3531130.3533349"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9944-y"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.053"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/080742270"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M153937X"},{"key":"e_1_2_1_27_1","volume-title":"Multi-Clique-Width. In Proc. ITCS 2017(Leibniz Int. Proc. Inform., Vol.\u00a0 67)","author":"F\u00fcrer Martin","year":"2017","unstructured":"Martin F\u00fcrer. 2017. Multi-Clique-Width. In Proc. ITCS 2017(Leibniz Int. Proc. Inform., Vol.\u00a0 67). 14:1\u201314:13. doi: 10.4230\/LIPIcs.ITCS.2017.14"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9751-3"},{"key":"e_1_2_1_29_1","volume-title":"Proc. STACS 2020(Leibniz Int. Proc. Inform., Vol.\u00a0 154)","author":"Gajarsk\u00fd Jakub","year":"2020","unstructured":"Jakub Gajarsk\u00fd and Stephan Kreutzer. 2020. Computing Shrub-Depth Decompositions. In Proc. STACS 2020(Leibniz Int. Proc. Inform., Vol.\u00a0 154). 56:1\u201356:17. doi: 10.4230\/LIPIcs.STACS.2020.56"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(1:7)2019"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.03.021"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.08.003"},{"key":"e_1_2_1_34_1","volume-title":"Proc. STACS 2020(Leibniz Int. Proc. Inform., Vol.\u00a0 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 Proc. STACS 2020(Leibniz Int. Proc. Inform., Vol.\u00a0 154)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Daniel\u00a0M. Kane. 2010. Unary Subset-Sum is in Logspace. CoRR abs\/1012.1336(2010). arXiv:1012.1336 http:\/\/arxiv.org\/abs\/1012.1336","DOI":"10.1055\/s-0030-1257927"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01005-y"},{"key":"e_1_2_1_37_1","volume-title":"Proc. WG 2011(Lecture Notes Comput. Sci., Vol.\u00a0 6986)","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh. 2011. Planar k-path in Subexponential Time and Polynomial Space. In Proc. WG 2011(Lecture Notes Comput. Sci., Vol.\u00a0 6986). 262\u2013270. doi: 10.1007\/978-3-642-25870-1_24"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_39_1","volume-title":"Proc. ESA 2022(Leibniz Int. Proc. Inform., Vol.\u00a0 244)","author":"Nadara Wojciech","year":"2022","unstructured":"Wojciech Nadara, Micha\u0142 Pilipczuk, and Marcin Smulewicz. 2022. Computing treedepth in polynomial space and linear FPT time. In Proc. ESA 2022(Leibniz Int. Proc. Inform., Vol.\u00a0 244). 79:1\u201379:14. doi: 10.4230\/lipics.esa.2022.79"},{"key":"e_1_2_1_40_1","volume-title":"Proc. WG 2020(Lecture Notes Comput. Sci., Vol.\u00a0 12301)","author":"Nederlof Jesper","year":"2020","unstructured":"Jesper Nederlof, Micha\u0142 Pilipczuk, C\u00e9line M.\u00a0F. Swennenhuis, and Karol W\u0119grzycki. 2020. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space. In Proc. WG 2020(Lecture Notes Comput. Sci., Vol.\u00a0 12301). 27\u201339. doi: 10.1007\/978-3-030-60440-0_3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.135"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","unstructured":"Patrice Ossona de Mendez Micha\u0142 Pilipczuk and Sebastian Siebertz. 2022. Transducing paths in graph classes with unbounded shrubdepth. European J. Combin. (2022) 103660. doi: 10.1016\/j.ejc.2022.103660","DOI":"10.1016\/j.ejc.2022.103660"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154856"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90026-4"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T10:29:09Z","timestamp":1742293749000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,18]]},"references-count":45,"alternative-id":["10.1145\/3723880"],"URL":"https:\/\/doi.org\/10.1145\/3723880","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,3,18]]},"assertion":[{"value":"2024-09-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3723880"}}