{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T11:53:46Z","timestamp":1772366026924,"version":"3.50.1"},"reference-count":19,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it, \u2026). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle\u2019s celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model checker for a small fragment of      MSO 1      (that is, we do not consider \u201cedge-set-based\u201d problems). This fragment is powerful enough to describe many natural problems, and our model checker turns out to be very competitive against similar state-of-the-art tools.<\/jats:p>","DOI":"10.3390\/a12080172","type":"journal-article","created":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T06:10:14Z","timestamp":1566195014000},"page":"172","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Practical Access to Dynamic Programming on Tree Decompositions"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6475-5512","authenticated-orcid":false,"given":"Max","family":"Bannach","sequence":"first","affiliation":[{"name":"Institute for Theoretical Computer Science, Universit\u00e4t zu L\u00fcbeck, 23562 L\u00fcbeck, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4177-8081","authenticated-orcid":false,"given":"Sebastian","family":"Berndt","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kiel University, 24103 Kiel, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_2","unstructured":"Dell, H., Husfeldt, T., Jansen, B.M.P., Kaski, P., Komusiewicz, C., and Rosamond, F.A. (2016, January 24\u201326). The first parameterized algorithms and computational experiments challenge. Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC), Aarhus, Denmark."},{"key":"ref_3","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., and Weller, M. (2017, January 6\u20138). The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), Vienna, Austria."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inf. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear-time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Tamaki, H. (2017, January 4\u20136). Positive-Instance driven dynamic programming for treewidth. Proceedings of the 25th Annual European Symposium on Algorithms (ESA), Vienna, Austria.","DOI":"10.1007\/s10878-018-0353-z"},{"key":"ref_7","unstructured":"Abseher, M., Bliem, B., Charwat, G., Dusberger, F., Hecher, M., and Woltran, S. (2019, June 05). D-FLAT: Progress Report. Available online: https:\/\/www.dbai.tuwien.ac.at\/research\/report\/dbai-tr-2014-86.pdf."},{"key":"ref_8","unstructured":"Langer, A.J. (2013). Fast Algorithms for Decomposable Graphs. [Ph.D. Thesis, The RWTH Aachen University]."},{"key":"ref_9","unstructured":"Diestel, R. (2012). Graph Theory: Springer Graduate Text Gtm 173, Springer. [4th ed.]."},{"key":"ref_10","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer."},{"key":"ref_11","unstructured":"Bannach, M., Berndt, S., and Ehlers, T. (2017, January 21\u201323). Jdrasil: A modular library for computing tree decompositions. Proceedings of the 16th International Symposium on Experimental Algorithms (SEA), London, UK."},{"key":"ref_12","unstructured":"Bannach, M. (2019, January 23). Jdrasil for Graph Coloring. Commit: a5e52a8."},{"key":"ref_13","unstructured":"Bannach, M., Berndt, S., and Ehlers, T. (2019, June 05). Jdrasil. Commit: dfa1eee."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","article-title":"The complexity of first-order and monadic second-order logic revisited","volume":"130","author":"Frick","year":"2004","journal-title":"Ann. Pure Appl. Logic"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.disopt.2011.06.001","article-title":"Courcelle\u2019s theorem\u2014A game-theoretic approach","volume":"8","author":"Kneis","year":"2011","journal-title":"Discret. Optim."},{"key":"ref_16","unstructured":"Bannach, M., and Berndt, S. (2019, April 08). Jatatosk. Available online: https:\/\/github.com\/maxbannach\/Jatatosk\/commit\/45e306cfac5a273416870ec0bd9cd2c7f39a6932."},{"key":"ref_17","unstructured":"Fichte, J.K. (2018, April 20). gtfs2graphs\u2014A Transit Feed to Graph Format Converter. Available online: https:\/\/github.com\/daajoe\/gtfs2graphs\/commit\/219944893f874b365de1ed87fc265fd5d19d5972."},{"key":"ref_18","unstructured":"Fichte, J.K., Lodha, N., and Szeider, S. (September, January 28). SAT-Based local improvement for finding tree decompositions of small width. Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT), Melbourne, Australia."},{"key":"ref_19","first-page":"275","article-title":"Improving the efficiency of dynamic programming on tree decompositions via machine learning","volume":"58","author":"Abseher","year":"2015","journal-title":"J. Artif. Intell. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/172\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:11:38Z","timestamp":1760188298000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,16]]},"references-count":19,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080172"],"URL":"https:\/\/doi.org\/10.3390\/a12080172","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,16]]}}}