{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:01:10Z","timestamp":1760241670763,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,7,1]],"date-time":"2018-07-01T00:00:00Z","timestamp":1530403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RO 927\/13"],"award-info":[{"award-number":["RO 927\/13"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Deutscher Akademischer Austauschdienst and Ministry of Science and Technology, Taiwand","award":["103-2911-I-194-506"],"award-info":[{"award-number":["103-2911-I-194-506"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth d cannot be bounded by (2\u2212\u03f5)d\u00b7logO(1)n for Vertex Cover, (3\u2212\u03f5)d\u00b7logO(1)n for 3-Coloring and (3\u2212\u03f5)d\u00b7logO(1)n for Dominating Set for any \u03f5&gt;0. This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth d: A pure branching algorithm that runs in time dO(d2)\u00b7n and uses space O(d3logd+dlogn) and a hybrid of branching and dynamic programming that achieves a running time of O(3dlogd\u00b7n) while using O(2ddlogd+dlogn) space.<\/jats:p>","DOI":"10.3390\/a11070098","type":"journal-article","created":{"date-parts":[[2018,7,2]],"date-time":"2018-07-02T10:56:52Z","timestamp":1530529012000},"page":"98","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming"],"prefix":"10.3390","volume":"11","author":[{"given":"Li-Hsuan","family":"Chen","sequence":"first","affiliation":[{"name":"AROBOT Innovation, Taiwan"}]},{"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, TW20 0EX, UK"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany"}]},{"given":"Fernando","family":"S\u00e1nchez Villaamil","sequence":"additional","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2018,7,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Duff, I. (1983). A multifrontal approach for solving sparse linear equations. Numerical Methods, Springer.","DOI":"10.1007\/BFb0112526"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1145\/356044.356047","article-title":"The multifrontal solution of indefinite sparse symmetric linear","volume":"9","author":"Duff","year":"1983","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1109\/TC.1982.1675979","article-title":"A data structure for parallel L\/U decomposition","volume":"31","author":"Jess","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"ref_4","unstructured":"Kees, H.G.M. (1982). The organization of circuit analysis on array architectures. [Ph.D. Thesis, Department of Electrical Engineering, Eindhoven University of Technology]."},{"key":"ref_5","unstructured":"Pieck, J.T.M. (1980). Formele Definitie Van Een E-Tree, Technische Hogeschool Eindhoven. Technical Report."},{"key":"ref_6","unstructured":"Pothen, A. (1988). The Complexity of Optimal Elimination Trees, Pennsylvannia State University. Technical Report."},{"key":"ref_7","unstructured":"Iyer, A.V., Ratliff, H.D., and Vijayan, G. (1986). On a Node Ranking Problem of Trees and Graphs. Technical Report, Georgia Inst of Tech Atlanta Production and Distribution Research Center. DTIC Document."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0166-218X(89)90025-5","article-title":"Local optimization on graphs","volume":"23","author":"Llewellyn","year":"1989","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/S0895480195282550","article-title":"Rankings of Graphs","volume":"11","author":"Bodlaender","year":"1998","journal-title":"SIAM J. Discret. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0012-365X(93)E0216-Q","article-title":"Ordered colourings","volume":"142","author":"Katchalski","year":"1995","journal-title":"Discret. Math."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., and Ossona de Mendez, P. (2012). Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bannister, M.J., Cabello, S., and Eppstein, D. (2013). Parameterized complexity of 1-planarity. Algorithms and Data Structures, Proceedings of the 13th International Symposium, WADS 2013, London, ON, Canada, 12\u201314 August 2013, Springer.","DOI":"10.1007\/978-3-642-40104-6_9"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gutin, G.Z., Jones, M., and Wahlstr\u00f6m, M. (2015, January 14\u201316). Structural Parameterizations of the Mixed Chinese Postman Problem. Proceedings of the Algorithms\u2014ESA 2015\u201423rd Annual European Symposium, Patras, Greece.","DOI":"10.1007\/978-3-662-48350-3_56"},{"key":"ref_14","unstructured":"Jasik, K. (2015). Treewidth on Fire. [Bachelor\u2019s Thesis, RWTH Aachen University]."},{"key":"ref_15","unstructured":"Wrochna, M. (arXiv, 2014). Reconfiguration in bounded bandwidth and treedepth, arXiv."},{"key":"ref_16","unstructured":"Demaine, E.D., Reidl, F., Rossmanith, P., S\u00e1nchez Villaamil, F., Sikdar, S., and Sullivan, B.D. (arXiv, 2014). Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs, arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s00224-017-9751-3","article-title":"Space Saving by Dynamic Algebraization Based on Tree-Depth","volume":"61","author":"Yu","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., and Saurabh, S. (2011, January 23\u201325). Known algorithms on graphs of bounded treewidth are probably optimal. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA.","DOI":"10.1137\/1.9781611973082.61"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. (1988). Dynamic Programming on Graphs With Bounded Treewidth, Springer.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. (1997). Treewidth: Algorithmic Techniques and Results, Springer.","DOI":"10.1007\/BFb0029946"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. (2012). Fixed-parameter tractability of treewidth and pathwidth. The Multivariate Algorithmic Revolution and Beyond, Springer.","DOI":"10.1007\/978-3-642-30891-8_12"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","article-title":"Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families","volume":"7","author":"Borie","year":"1992","journal-title":"Algorithmica"},{"key":"ref_23","first-page":"4","article-title":"Solving problems on recursively constructed graphs","volume":"41","author":"Borie","year":"2008","journal-title":"ACM Comput. Surv."},{"key":"ref_24","unstructured":"Scheffler, P. (1986). Dynamic Programming Algorithms for Tree-Decomposition Problems, Akad. d. Wissensch. d. DDR. Institut f\u00fcr Mathematik."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","article-title":"Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs","volume":"8","author":"Bern","year":"1987","journal-title":"J. Algorithms"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0097-3165(73)90016-2","article-title":"On non-serial dynamic programming","volume":"14","author":"Bertele","year":"1973","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Rooij, J.V., Bodlaender, H., and Rossmanith, P. (2009). Dynamic programming on tree decompositions using generalised fast subset convolution. Algorithms-ESA 2009, Proceedings of the 17th Annual European Symposium, Copenhagen, Denmark, 7\u20139 September 2009, Springer. Number 5193 in LNCS.","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/s00037-011-0028-y","article-title":"Toward a model for backtracking and dynamic programming","volume":"20","author":"Alekhnovich","year":"2011","journal-title":"Comput. Complex."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1007\/s00453-009-9385-1","article-title":"A stronger model of dynamic programming algorithms","volume":"60","author":"Davis","year":"2011","journal-title":"Algorithmica"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/58562.59304","article-title":"A common schema for dynamic programming and branch and bound algorithms","volume":"36","author":"Helman","year":"1989","journal-title":"J. ACM"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1137\/0115060","article-title":"Finite-state processes and dynamic programming","volume":"15","author":"Karp","year":"1967","journal-title":"SIAM J. Appl. Math."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/2925416","article-title":"On problems as hard as CNF-SAT","volume":"12","author":"Cygan","year":"2016","journal-title":"ACM Trans. Algorithms"},{"key":"ref_33","unstructured":"Nederlof, J. (2011). Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms. [Ph.D. Thesis, University of Bergen]."},{"key":"ref_34","unstructured":"Drucker, A., Nederlof, J., and Santhanam, R. (2016, January 22\u201324). Exponential Time Paradigms Through the Polynomial Time Lens. Proceedings of the 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., and Nederlof, J. (2010, January 6\u20138). Saving space by algebraization. Proceedings of the 42th ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806735"},{"key":"ref_36","first-page":"57:1","article-title":"On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs","volume":"Volume 47","author":"Ollinger","year":"2016","journal-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2010). Graph Theory, Springer. [4th ed.].","DOI":"10.1007\/978-3-642-14279-6"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Lindell, S. (1992, January 4\u20136). A logspace algorithm for tree canonization. Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada.","DOI":"10.1145\/129712.129750"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., and Koivisto, M. (2007, January 11\u201313). Fourier meets M\u00f6bius: Fast subset convolution. Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/1250790.1250801"},{"key":"ref_40","unstructured":"Oelschl\u00e4gel, T. (2016). Graph Partitioning Problems on Graphs of Bounded Treedepth. [Master\u2019s Thesis, RWTH Aachen University]."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","article-title":"Algorithms for vertex partitioning problems on partial k-trees","volume":"10","author":"Telle","year":"1997","journal-title":"SIAM J. Discret. Math."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","article-title":"Algorithmic meta-theorems for restrictions of treewidth","volume":"64","author":"Lampis","year":"2012","journal-title":"Algorithmica"},{"key":"ref_43","unstructured":"Gajarsky, J., and Hlin\u011bn\u00fd, P. (2012, January 15\u201317). Faster deciding MSO properties of trees of fixed height, and some consequences. Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), Hyderabad, India."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/98\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:10:54Z","timestamp":1760195454000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/98"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,1]]},"references-count":43,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["a11070098"],"URL":"https:\/\/doi.org\/10.3390\/a11070098","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,7,1]]}}}