{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:48:19Z","timestamp":1780822099449,"version":"3.54.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,31]],"date-time":"2017-12-31T00:00:00Z","timestamp":1514678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Foundation for Polish Science via the START stipend programme"},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["DEC-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["DEC-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>\n            Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition\u2019s width. Following the work of Allender et al. [5], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [18], we prove that the question is closely related to a conjecture that the L\n            <jats:sc>ongest<\/jats:sc>\n            C\n            <jats:sc>ommon<\/jats:sc>\n            S\n            <jats:sc>ubsequence<\/jats:sc>\n            problem parameterized by the number of input strings does not admit an algorithm that simultaneously uses\n            <jats:bold>XP<\/jats:bold>\n            time and\n            <jats:bold>FPT<\/jats:bold>\n            space. Moreover, we extend the complexity landscape sketched for pathwidth and treewidth by Allender et al. by considering the parameter\n            <jats:italic>tree-depth<\/jats:italic>\n            . We prove that computations on tree-depth decompositions correspond to a model of non-deterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition\u2019s depth. Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomial-time non-deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and tree-depth.\n          <\/jats:p>","DOI":"10.1145\/3154856","type":"journal-article","created":{"date-parts":[[2018,1,12]],"date-time":"2018-01-12T13:49:50Z","timestamp":1515764990000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs"],"prefix":"10.1145","volume":"9","author":[{"given":"Micha\u0142","family":"Pilipczuk","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9346-2172","authenticated-orcid":false,"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,1,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1885577.1885583"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.013"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a012"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_7_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793283151"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBE.2007.4375584"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.05.008"},{"key":"e_1_2_1_13_1","volume-title":"Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161","author":"Bj\u00f6rklund Andreas","year":"2010"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195282550"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00251-D"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1156"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00074-6"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC\u201915)","volume":"9472","author":"Chakraborty Diptarka","year":"2015"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603107"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001119"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_23_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_25_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999"},{"key":"e_1_2_1_26_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795295948"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.37"},{"key":"e_1_2_1_29_1","first-page":"62","article-title":"Logspace versions of the theorems of bodlaender and courcelle","volume":"17","author":"Elberfeld Michael","year":"2010","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","volume":"14","author":"Elberfeld Michael","year":"2012"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9944-y"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory (1 ed.). Springer.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory (1 ed.). Springer.","DOI":"10.2168\/LMCS-1(1:2)2005"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_40"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06686-8_29"},{"key":"e_1_2_1_35_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.08.003"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0216-Q"},{"key":"e_1_2_1_40_1","volume-title":"Lecture Notes in Computer Science","author":"Kloks Ton"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10046"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2014.08.001"},{"key":"e_1_2_1_43_1","volume-title":"The P&equals;NP Question and G\u00f6del\u2019s Lost Letter","author":"Lipton Richard J."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25870-1_24"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_77"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/6566.6568"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205052"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.09.012"},{"key":"e_1_2_1_54_1","first-page":"124","article-title":"The depth irreducibility hypothesis","volume":"21","author":"Papakonstantinou Periklis A.","year":"2014","journal-title":"Proceedings of the Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_58_1","article-title":"Approximate formulas for some functions of prime numbers","volume":"6","author":"Barkley Rosser J.","year":"1962","journal-title":"Illinois J. Math."},{"key":"e_1_2_1_59_1","volume-title":"Foundations of Artificial Intelligence","volume":"2","author":"Rossi Francesca","year":"2006"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90036-7"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 10th Conference on Foundations of Software Technology and Theoretical Computer Science (Lecture Notes in Computer Science)","volume":"472","author":"Vinay V."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/645721.666377"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154856","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:38Z","timestamp":1750213598000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,31]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3154856"],"URL":"https:\/\/doi.org\/10.1145\/3154856","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,31]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}