{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:35Z","timestamp":1775184815797,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["101071674"],"award-info":[{"award-number":["101071674"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ministry for Innovation and Technology, Hungary","award":["TKP2021-NVA-09"],"award-info":[{"award-number":["TKP2021-NVA-09"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs defined over\n            <jats:italic>k<\/jats:italic>\n            -types, for a sufficiently large\n            <jats:italic>k<\/jats:italic>\n            . We give sufficient conditions when this method can be applied and apply these conditions to obtain a new complexity dichotomy for CSPs of first-order expansions of the basic relations of the well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion.\n          <\/jats:p>","DOI":"10.1145\/3649445","type":"journal-article","created":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T12:09:46Z","timestamp":1709294986000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":false,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algebra, Fakult\u00e4t f\u00fcr Mathematik, TU Dresden, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6679-6355","authenticated-orcid":false,"given":"Bertalan","family":"Bodor","sequence":"additional","affiliation":[{"name":"Department of Algebra and Number Theory, University of Szeged, Szeged, Hungary"}]}],"member":"320","published-online":{"date-parts":[[2024,6,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.049"},{"key":"e_1_3_3_3_2","volume-title":"Proceedings of the Symposium on Logic in Computer Science.","author":"Bodirsky Manuel","year":"2021","unstructured":"Manuel Bodirsky and Bertalan Bodor. 2021. Canonical polymorphisms of Ramsey structures and the unique interpolation property. In Proceedings of the Symposium on Logic in Computer Science."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1515\/jgth-2018-0220"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"1359","DOI":"10.1093\/logcom\/exp025","article-title":"Qualitative temporal and spatial reasoning revisited","volume":"19","author":"Bodirsky Manuel","year":"2009","unstructured":"Manuel Bodirsky and Hubie Chen. 2009. Qualitative temporal and spatial reasoning revisited. Journal of Logic and Computation 19, 6 (2009), 1359\u20131383.","journal-title":"Journal of Logic and Computation"},{"key":"e_1_3_3_6_2","first-page":"62","volume-title":"Proceedings of the International Conference on Knowledge Representation and Reasoning","author":"Bennett Brandon","year":"1994","unstructured":"Brandon Bennett. 1994. Spatial reasoning with propositional logics. In Proceedings of the International Conference on Knowledge Representation and Reasoning, pages 51\u201362. Morgan Kaufmann."},{"key":"e_1_3_3_7_2","first-page":"1","article-title":"On the scope of the universal-algebraic approach to constraint satisfaction","volume":"8","author":"Bodirsky Manuel","year":"2012","unstructured":"Manuel Bodirsky, Martin Hils, and Barnaby Martin. 2012. On the scope of the universal-algebraic approach to constraint satisfaction. Logical Methods in Computer Science 8, 3 (2012), 1\u201330. An extended abstract that announced some of the results appeared in the proceedings of Logic in Computer Science (LICS\u201910).","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5260"},{"key":"e_1_3_3_9_2","article-title":"The complexity of phylogeny constraint satisfaction problems","volume":"18","author":"Bodirsky Manuel","year":"2017","unstructured":"Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. 2017. The complexity of phylogeny constraint satisfaction problems. ACM Transactions on Computational Logic 18, 3 (2017). An extended abstract appeared in the conference STACS 2016, 20:1\u201320:13.","journal-title":"ACM Transactions on Computational Logic"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"e_1_3_3_11_2","first-page":"603","volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science.","author":"Barto Libor","year":"2009","unstructured":"Libor Barto and Marcin Kozik. 2009. Constraint satisfaction problems of bounded width. In Proceedings of the Annual Symposium on Foundations of Computer Science. pages 595\u2013603."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_3_3_13_2","first-page":"1","article-title":"Absorbing subalgebras, cyclic terms and the constraint satisfaction problem","volume":"8","author":"Barto Libor","year":"2012","unstructured":"Libor Barto and Marcin Kozik. 2012. Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods in Computer Science 8\/1, 07 (2012), 1\u201326.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","article-title":"Classifying the complexity of constraints using finite algebras","volume":"34","author":"Bulatov Andrei A.","year":"2005","unstructured":"Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons. 2005. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing 34, 3 (2005), 720\u2013742.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_16_2","volume-title":"Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science. Preprint arXiv:1612","author":"Barto Libor","year":"2017","unstructured":"Libor Barto, Michael Kompatscher, Miroslav Ol\u0161\u00e1k, Trung Van Pham, and Michael Pinsker. 2017. The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science. Preprint arXiv:1612.07551."},{"key":"e_1_3_3_17_2","article-title":"Equations in oligomorphic clones and the constraint satisfaction problem for  \\(\\omega\\) -categorical structures","volume":"19","author":"Barto Libor","year":"2019","unstructured":"Libor Barto, Michael Kompatscher, Miroslav Ol\u0161\u00e1k, Trung Van Pham, and Michael Pinsker. 2019. Equations in oligomorphic clones and the constraint satisfaction problem for \\(\\omega\\) -categorical structures. Journal of Mathematical Logic 19, 2 (2019), #1950010.","journal-title":"Journal of Mathematical Logic"},{"key":"e_1_3_3_18_2","first-page":"1","article-title":"A dichotomy for first-order reducts of unary structures","volume":"14","author":"Bodirsky Manuel","year":"2018","unstructured":"Manuel Bodirsky and Antoine Mottet. 2018. A dichotomy for first-order reducts of unary structures. Logical Methods in Computer Science 14, 2 (2018), 1\u201331.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_19_2","first-page":"114","volume-title":"Proceedings of the Symposium on Logic in Computer Science.","author":"Bodirsky Manuel","year":"2018","unstructured":"Manuel Bodirsky, Florent Madelaine, and Antoine Mottet. 2018. A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP. In Proceedings of the Symposium on Logic in Computer Science. pages 105\u2013114. Preprint arXiv:1802.03255."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082974"},{"key":"e_1_3_3_21_2","first-page":"1","article-title":"Cores of countably categorical structures","volume":"3","author":"Bodirsky Manuel","year":"2007","unstructured":"Manuel Bodirsky. 2007. Cores of countably categorical structures. Logical Methods in Computer Science 3, 1 (2007), 1\u201316.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_22_2","volume-title":"Proceedings of the Surveys in Combinatorics","author":"Bodirsky Manuel","year":"2015","unstructured":"Manuel Bodirsky. 2015. Ramsey classes: Examples and constructions. In Proceedings of the Surveys in Combinatorics. London Mathematical Society Lecture Note Series 424. Cambridge University Press, 2015. Invited survey article for the British Combinatorial Conference; ArXiv:1502.05146."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2023.66"},{"key":"e_1_3_3_24_2","series-title":"Lecture Notes in Logic (52)","volume-title":"Complexity of Infinite-Domain Constraint Satisfaction","author":"Bodirsky Manuel","unstructured":"Manuel Bodirsky. 2021. Complexity of Infinite-Domain Constraint Satisfaction. Lecture Notes in Logic (52). Cambridge University Press, Cambridge, United Kingdom; New York, NY."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_3_27_2","first-page":"519","volume-title":"AMS Contemporary Mathematics","volume":"558","author":"Bodirsky Manuel","year":"2011","unstructured":"Manuel Bodirsky and Michael Pinsker. 2011. Reducts of Ramsey structures. AMS Contemporary Mathematics, vol. 558 (Model Theoretic Methods in Finite Combinatorics) 558 (2011), pages 489\u2013519."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1216213"},{"key":"e_1_3_3_30_2","volume-title":"Homogeneous Structures, A Workshop in Honour of Norbert Sauer\u2019s 70th Birthday, Contributions to Discrete Mathematics 16","author":"Bodirsky Manuel","year":"2021","unstructured":"Manuel Bodirsky and Michael Pinsker. 2021. Canonical functions: A proof via topological dynamics. Homogeneous Structures, A Workshop in Honour of Norbert Sauer\u2019s 70th Birthday, Contributions to Discrete Mathematics 16, 2 (2021), 36\u201345."},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1017\/jsl.2019.23","article-title":"Projective clone homomorphisms","volume":"86","author":"Bodirsky Manuel","year":"2021","unstructured":"Manuel Bodirsky, Michael Pinsker, and Andr\u00e1s Pongr\u00e1cz. 2021. Projective clone homomorphisms. Journal of Symbolic Logic 86, 1 (2021), 148\u2013161.","journal-title":"Journal of Symbolic Logic"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.2178\/jsl.7804020","article-title":"Decidability of definability","volume":"78","author":"Bodirsky Manuel","year":"2011","unstructured":"Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. 2011. Decidability of definability. Journal of Symbolic Logic 78, 4 (2013), 1036\u20131054. A conference version appeared in the Proceedings of the Twenty-Sixth Annual IEEE Symposium on. Logic in Computer Science (LICS 2011), pages 321-328.","journal-title":"Journal of Symbolic Logic"},{"key":"e_1_3_3_33_2","article-title":"On the descriptive complexity of temporal constraint satisfaction problems","volume":"70","author":"Bodirsky Manuel","year":"2023","unstructured":"Manuel Bodirsky and Jakub Rydval. 2023. On the descriptive complexity of temporal constraint satisfaction problems. Journal of the ACM 70, 1 (2023), 2:1\u20132:58. A conference version of this article appear under the title \u201cTemporal Constraint Satisfaction Problems in Fixed-Point Logic\u201d in LICS\u201920.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1112\/plms.12429","article-title":"Monadic stability and growth rates of  \\(\\omega\\) -categorical structures","volume":"124","author":"Braunfeld Samuel","year":"2022","unstructured":"Samuel Braunfeld. 2022. Monadic stability and growth rates of \\(\\omega\\) -categorical structures. Proceedings of the London Mathematical Society, Series B 124, 3 (2022), 373\u2013386. Preprint arXiv:1910.04380.","journal-title":"Proceedings of the London Mathematical Society, Series B"},{"key":"e_1_3_3_35_2","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science","author":"Bulatov Andrei A.","year":"2017","unstructured":"Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA, October 15\u201317, pages 319\u2013330."},{"key":"e_1_3_3_36_2","series-title":"CUP Archive","volume-title":"Commutator Theory for Congruence Modular Varieties","author":"Freese Ralph","unstructured":"Ralph Freese and Ralph McKenzie. 1987. Commutator Theory for Congruence Modular Varieties, volume 125 of CUP Archive. Cambridge University Press."},{"key":"e_1_3_3_37_2","first-page":"03489","article-title":"The orbit algebra of a permutation group with polynomial profile is Cohen-Macaulay","volume":"1804","author":"Falque Justine","year":"2018","unstructured":"Justine Falque and Nicolas M. Thi\u00e9ry. 2018. The orbit algebra of a permutation group with polynomial profile is Cohen-Macaulay. Preprint ArXiv:1804.03489.","journal-title":"Preprint ArXiv"},{"key":"e_1_3_3_38_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","article-title":"The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory","volume":"28","author":"Feder Tom\u00e1s","year":"1999","unstructured":"Tom\u00e1s Feder and Moshe Y. Vardi. 1999. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28, 1 (1999), 57\u2013104.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_39_2","volume-title":"A Shorter Model Theory","author":"Hodges Wilfrid","unstructured":"Wilfrid Hodges. 1997. A Shorter Model Theory. Cambridge University Press, Cambridge."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622767.1622774"},{"key":"e_1_3_3_41_2","volume-title":"A complexity dichotomy for poset constraint satisfaction. IfCoLog Journal of Logics and their Applications 5, 8","author":"Kompatscher Michael","year":"2018","unstructured":"Michael Kompatscher and Trung Van Pham. A complexity dichotomy for poset constraint satisfaction. IfCoLog Journal of Logics and their Applications 5, 8 (2018), 1663\u20131696."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0503-1"},{"key":"e_1_3_3_43_2","doi-asserted-by":"crossref","first-page":"501","DOI":"10.2307\/2275284","article-title":"\\(\\aleph _0\\) -categorical tree-decomposable structures","volume":"57","author":"Lachlan Alistair H.","year":"1992","unstructured":"Alistair H. Lachlan. 1992. \\(\\aleph _0\\) -categorical tree-decomposable structures. The Journal of Symbolic Logic 57, 2 (1992), 501\u2013514.","journal-title":"The Journal of Symbolic Logic"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"e_1_3_3_45_2","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, July 12-16, 2021, Glasgow, Scotland (Virtual Conference)","volume":"198","author":"Mottet Antoine","year":"2021","unstructured":"Antoine Mottet, Tom\u00e1s Nagy, Michael Pinsker, and Michal Wrona. 2021. Smooth approximations and relational width collapses. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, Nikhil Bansal, Emanuela Merelli, and James Worrell, (Eds.), pages 138:1\u2013138:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2021.6"},{"key":"e_1_3_3_47_2","volume-title":"Proceedings of the Symposium on Logic in Computer Science. Preprint arXiv:2011","author":"Mottet Antoine","year":"2022","unstructured":"Antoine Mottet and Michael Pinsker. 2022. Smooth approximations and CSPs over finitely bounded homogeneous structures. In Proceedings of the Symposium on Logic in Computer Science. Preprint arXiv:2011.03978."},{"key":"e_1_3_3_48_2","first-page":"244","volume-title":"Proceedings of the Advances in Artificial Intelligence, 19th Annual German Conference on Artificial Intelligence, Bielefeld, Germany, September 11\u201313, 1995","author":"Nebel Bernhard","year":"1995","unstructured":"Bernhard Nebel. 1995. Computational properties of qualitative spatial reasoning: First results. In Proceedings of the Advances in Artificial Intelligence, 19th Annual German Conference on Artificial Intelligence, Bielefeld, Germany, September 11\u201313, 1995, Proceedings, pages 233\u2013244."},{"key":"e_1_3_3_49_2","volume-title":"The Two-valued Iterative Systems of Mathematical Logic","author":"Post Emil L.","unstructured":"Emil L. Post. 1941. The Two-valued Iterative Systems of Mathematical Logic, volume 5. Princeton University Press, Princeton."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622845.1622854"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-010-0082-3"},{"key":"e_1_3_3_52_2","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Zhuk Dmitriy N.","year":"2017","unstructured":"Dmitriy N. Zhuk. 2017. A proof of CSP dichotomy conjecture. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, pages 331\u2013342. https:\/\/arxiv.org\/abs\/1704.01914"},{"key":"e_1_3_3_53_2","unstructured":"Dmitriy Zhuk. 2020. Strong subalgebras and the constraint satisfaction problem. arXiv:2005.00593. Retrieved from https:\/\/arxiv.org\/abs\/2005.00593"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:21Z","timestamp":1750291401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3649445"],"URL":"https:\/\/doi.org\/10.1145\/3649445","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2022-02-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}