{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T23:28:18Z","timestamp":1771889298533,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,6,3]],"date-time":"2022-06-03T00:00:00Z","timestamp":1654214400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,3]],"date-time":"2022-06-03T00:00:00Z","timestamp":1654214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P30930"],"award-info":[{"award-number":["P30930"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Constraint Satisfaction Problems (CSP) are notoriously hard. Consequently, powerful decomposition methods have been developed to overcome this complexity. However, this poses the challenge of actually computing such a decomposition for a given CSP instance, and previous algorithms have shown their limitations in doing so. In this paper, we present a number of key algorithmic improvements and parallelisation techniques to compute so-called Generalized Hypertree Decompositions (GHDs) faster. We thus advance the ability to compute optimal (i.e., minimal-width) GHDs for a significantly wider range of CSP instances on modern machines. This lays the foundation for more systems and applications in evaluating CSPs and related problems (such as Conjunctive Query answering) based on their structural properties.<\/jats:p>","DOI":"10.1007\/s10601-022-09332-1","type":"journal-article","created":{"date-parts":[[2022,6,3]],"date-time":"2022-06-03T06:02:31Z","timestamp":1654236151000},"page":"284-326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Fast and parallel decomposition of constraint satisfaction problems"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2353-5230","authenticated-orcid":false,"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7742-0439","authenticated-orcid":false,"given":"Cem","family":"Okulmus","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,3]]},"reference":[{"key":"9332_CR1","doi-asserted-by":"crossref","unstructured":"Aberger, C. R., Tu, S., Olukotun, K., & R\u00e9, C. (2016). Emptyheaded: A relational engine for graph processing. In Proceedings of the 2016 international conference on management of data, SIGMOD conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, (pp. 431\u2013446).","DOI":"10.1145\/2882903.2915213"},{"issue":"8","key":"9332_CR2","doi-asserted-by":"publisher","first-page":"2167","DOI":"10.1016\/j.ejc.2007.04.013","volume":"28","author":"I Adler","year":"2007","unstructured":"Adler, I., Gottlob, G., & Grohe, M. (2007). Hypertree width and related hypergraph invariants. European Journal of Combinatorics, 28(8), 2167\u20132181.","journal-title":"European Journal of Combinatorics"},{"key":"9332_CR3","volume-title":"Exploiting parallelism in decomposition methods for constraint satisfaction","author":"D Akatov","year":"2010","unstructured":"Akatov, D. (2010). Exploiting parallelism in decomposition methods for constraint satisfaction. UK: Ph.D. thesis, University of Oxford. https:\/\/ora.ox.ac.uk\/objects\/uuid:30773f0c-9b53-4684-b1c4-2d20c2322edd."},{"issue":"2","key":"9332_CR4","doi-asserted-by":"publisher","first-page":"371","DOI":"10.3233\/AIC-150694","volume":"29","author":"K Amroun","year":"2016","unstructured":"Amroun, K., Habbas, Z., & Aggoune-mtalaa, W. (2016). A compressed generalized hypertree decomposition-based solving technique for non-binary constraint satisfaction problems. AI Comm., 29(2), 371\u2013392.","journal-title":"AI Comm."},{"key":"9332_CR5","doi-asserted-by":"crossref","unstructured":"Aref, M., ten Cate, B., Green, T. J., Kimelfeld, B., Olteanu, D., Pasalic, E., Veldhuizen, T. L., & Washburn, G. (2015). Design and implementation of the logicblox system. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, (pp. 1371\u20131382).","DOI":"10.1145\/2723372.2742796"},{"key":"9332_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752","volume-title":"Term Rewriting and All That","author":"F Baader","year":"1998","unstructured":"Baader, F., & Nipkow, T. (1998). Term Rewriting and All That. Cambridge: Cambridge University Press."},{"issue":"6","key":"9332_CR7","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L. (1996). A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6), 1305\u20131317. https:\/\/doi.org\/10.1137\/S0097539793251219.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9332_CR8","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1016\/j.jcss.2007.08.001","volume":"74","author":"DA Cohen","year":"2008","unstructured":"Cohen, D. A., Jeavons, P., & Gyssens, M. (2008). A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer and System Sciences, 74(5), 721\u2013743.","journal-title":"Journal of Computer and System Sciences"},{"key":"9332_CR9","unstructured":"Cox-Buday, K. (2017). Concurrency in Go: Tools and techniques for developers. \u201cO\u2019Reilly Media Inc.\u201d."},{"key":"9332_CR10","unstructured":"Donovan, A. A. A., & Kernighan, B. W. (2015). The Go programming language. Addison-Wesley Professional."},{"key":"9332_CR11","unstructured":"Dzulfikar, M. A., Fichte, J. K., & Hecher, M. (2019). The PACE 2019 parameterized algorithms and computational experiments challenge: The fourth iteration (invited paper). In 14Th international symposium on parameterized and exact computation, IPEC 2019, september 11-13, 2019, munich, germany, (pp. 25:1\u201325:23)."},{"issue":"3","key":"9332_CR12","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R Fagin","year":"1983","unstructured":"Fagin, R. (1983). Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30(3), 514\u2013550. https:\/\/doi.org\/10.1145\/2402.322390.","journal-title":"J. ACM"},{"key":"9332_CR13","doi-asserted-by":"crossref","unstructured":"Fichte, J. K., Hecher, M., Lodha, N., & Szeider, S. (2018). An SMT approach to fractional hypertree width. In Principles and practice of constraint programming - 24th international conference, CP 2018, lille, france, august 27-31, 2018, proceedings, (pp. 109\u2013127).","DOI":"10.1007\/978-3-319-98334-9_8"},{"key":"9332_CR14","doi-asserted-by":"publisher","unstructured":"Fischl, W., Gottlob, G., Longo, D. M., & Pichler, R. (2021). HyperBench: A benchmark and tool for hypergraphs and empirical findings. ACM J. Exp. Algorithmics 26. https:\/\/doi.org\/10.1145\/3440015.","DOI":"10.1145\/3440015"},{"key":"9332_CR15","doi-asserted-by":"crossref","unstructured":"Fischl, W., Gottlob, G., & Pichler, R. (2018). General and fractional hypertree decompositions: Hard and easy cases. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, (pp. 17\u201332).","DOI":"10.1145\/3196959.3196962"},{"issue":"6","key":"9332_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.","journal-title":"Communications of the ACM"},{"key":"9332_CR17","unstructured":"Gottlob, G., Hutle, M., & Wotawa, F. (2002). Combining hypertree, bicomp, and hinge decomposition. In Proceedings of the 15th European Conference on Artificial Intelligence, ECAI 2002, (pp. 161\u2013165). IOS Press."},{"issue":"2","key":"9332_CR18","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2), 243\u2013282.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"9332_CR19","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (2002). Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3), 579\u2013627.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"9332_CR20","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/1568318.1568320","volume":"56","author":"G Gottlob","year":"2009","unstructured":"Gottlob, G., Mikl\u00f3s, Z., & Schwentick, T. (2009). Generalized hypertree decompositions: NP-hardness and tractable variants. J. ACM, 56(6), 30:1\u201330:32.","journal-title":"J. ACM"},{"key":"9332_CR21","doi-asserted-by":"publisher","unstructured":"Gottlob, G., Okulmus, C., & Pichler, R. (2020). Fast and parallel decomposition of constraint satisfaction problems. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, (pp. 1155\u20131162). https:\/\/doi.org\/10.24963\/ijcai.2020\/161.","DOI":"10.24963\/ijcai.2020\/161"},{"key":"9332_CR22","doi-asserted-by":"publisher","unstructured":"Gottlob, G., Okulmus, C., & Pichler, R. (2021). Raw data on extended experiments for balancedgo zenodo. https:\/\/doi.org\/10.5281\/zenodo.4411863.","DOI":"10.5281\/zenodo.4411863"},{"key":"9332_CR23","doi-asserted-by":"publisher","unstructured":"Gottlob, G., & Samer, M. (2008). A backtracking-based algorithm for hypertree decomposition. ACM J. Exp. Algorithmics 13. https:\/\/doi.org\/10.1145\/1412228.1412229.","DOI":"10.1145\/1412228.1412229"},{"key":"9332_CR24","unstructured":"Graham, M. H. (1979). On the universal relation. Tech. rep. University of Toronto."},{"issue":"1","key":"9332_CR25","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2636918","volume":"11","author":"M Grohe","year":"2014","unstructured":"Grohe, M., & Marx, D. (2014). Constraint solving via fractional edge covers. ACM Trans. Algorithms, 11(1), 4:1\u20134:20. https:\/\/doi.org\/10.1145\/2636918.","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9332_CR26","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M Gyssens","year":"1994","unstructured":"Gyssens, M., Jeavons, P., & Cohen, D. A. (1994). Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence, 66 (1), 57\u201389.","journal-title":"Artificial Intelligence"},{"issue":"5","key":"9332_CR27","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1080\/0952813X.2014.993507","volume":"27","author":"Z Habbas","year":"2015","unstructured":"Habbas, Z., Amroun, K., & Singer, D. (2015). A forward-checking algorithm based on a generalised hypertree decomposition for solving non-binary constraint satisfaction problems. J. Exp. Theor. Artif. Intell., 27(5), 649\u2013671.","journal-title":"J. Exp. Theor. Artif. Intell."},{"issue":"8","key":"9332_CR28","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1145\/359576.359585","volume":"21","author":"CAR Hoare","year":"1978","unstructured":"Hoare, C. A. R. (1978). Communicating sequential processes. Communications of the ACM, 21(8), 666\u2013677.","journal-title":"Communications of the ACM"},{"key":"9332_CR29","doi-asserted-by":"publisher","unstructured":"Kloks, T. (1994). Treewidth, computations and approximations. In Lecture notes in computer science, (vol. 842). Springer.https:\/\/doi.org\/10.1007\/BFb0045375.","DOI":"10.1007\/BFb0045375"},{"issue":"2","key":"9332_CR30","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"PG Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., & Vardi, M.Y. (2000). Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci., 61(2), 302\u2013332. https:\/\/doi.org\/10.1006\/jcss.2000.1713.","journal-title":"J. Comput. Syst. Sci."},{"key":"9332_CR31","doi-asserted-by":"publisher","unstructured":"Korhonen, T., Berg, J., & J\u00e4rvisalo, M. (2019). Enumerating potential maximal cliques via SAT and ASP. In S. Kraus (Ed.) Proceedings of the twenty-eighth international joint conference on artificial intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, (pp. 1116\u20131122).https:\/\/doi.org\/10.24963\/ijcai.2019\/156.","DOI":"10.24963\/ijcai.2019\/156"},{"key":"9332_CR32","doi-asserted-by":"publisher","unstructured":"Lagergren, J. (1990). Efficient parallel algorithms for tree-decomposition and related problems. In 31st Annual symposium on foundations of computer science, St. Louis, Missouri, USA, October 22-24, 1990, (Vol. I, pp. 173\u2013182). IEEE Computer Society.https:\/\/doi.org\/10.1109\/FSCS.1990.89536.","DOI":"10.1109\/FSCS.1990.89536"},{"key":"9332_CR33","unstructured":"Lalou, M., Habbas, Z., & Amroun, K. (2009). Solving hypertree structured CSP: sequential and parallel approaches. In Proceedings of the 16th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, RCRA@AI*IA 2009, Reggio Emilia, Italy, December 11-12, 2009, CEUR Workshop Proceedings, vol. 589. CEUR-WS.org."},{"key":"9332_CR34","doi-asserted-by":"publisher","unstructured":"Longo, D.M. (2019). Pace2019 hypertree width heuristic. https:\/\/doi.org\/10.5281\/zenodo.3236369.","DOI":"10.5281\/zenodo.3236369"},{"issue":"6","key":"9332_CR35","doi-asserted-by":"publisher","first-page":"42:1","DOI":"10.1145\/2535926","volume":"60","author":"D Marx","year":"2013","unstructured":"Marx, D. (2013). Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM, 60(6), 42:1\u201342:51.","journal-title":"J. ACM"},{"key":"9332_CR36","unstructured":"Meiri, I., Pearl, J., & Dechter, R. (1990). Tree decomposition with applications to constraint processing. In Proceedings of the 8th national conference on artificial intelligence. Boston, Massachusetts, USA, July 29 - August 3, 1990, 2 Volumes, (pp. 10\u201316). AAAI Press \/ The MIT Press.http:\/\/www.aaai.org\/Library\/AAAI\/1990\/aaai90-002.php."},{"key":"9332_CR37","doi-asserted-by":"publisher","unstructured":"Robertson, N., & Seymour, P.D. (1986). Graph minors. II. algorithmic aspects of tree-width, (Vol. 7. https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4.","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"9332_CR38","doi-asserted-by":"publisher","unstructured":"Schidler, A., & Szeider, S. (2020). Computing optimal hypertree decompositions. In Proceedings of the symposium on algorithm engineering and experiments, ALENEX 2020, Salt Lake City, UT, USA, January 5-6, 2020, (pp. 1\u201311). SIAM.https:\/\/doi.org\/10.1137\/1.9781611976007.1.","DOI":"10.1137\/1.9781611976007.1"},{"issue":"2-4","key":"9332_CR39","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/cpe.938","volume":"17","author":"D Thain","year":"2005","unstructured":"Thain, D., Tannenbaum, T., & Livny, M. (2005). Distributed computing in practice: the Condor experience. Concurrency - Practice and Experience, 17(2-4), 323\u2013356.","journal-title":"Concurrency - Practice and Experience"},{"issue":"1","key":"9332_CR40","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S. (1962). A theorem on boolean matrices. Journal of the ACM, 9(1), 11\u201312.","journal-title":"Journal of the ACM"},{"key":"9332_CR41","unstructured":"Yannakakis, M. (1981). Algorithms for acyclic database schemes. In Very large data bases, 7th international conference, September 9-11, 1981, Cannes, France, Proceedings, (pp. 82\u201394)."},{"key":"9332_CR42","doi-asserted-by":"crossref","unstructured":"Yu, C. T., & \u00d6zsoyo\u011flu, M. Z. (1979). An algorithm for tree-query membership of a distributed query. In The EEE computer society\u2019s third international computer software and applications conference, COMPSAC 1979, 6-8 November, 1979, Chicago, Illinois, USA, (pp. 306\u2013312).","DOI":"10.1109\/CMPSAC.1979.762509"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-022-09332-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-022-09332-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-022-09332-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T11:31:01Z","timestamp":1662118261000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-022-09332-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,3]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["9332"],"URL":"https:\/\/doi.org\/10.1007\/s10601-022-09332-1","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,3]]},"assertion":[{"value":"23 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}