{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:14:44Z","timestamp":1787390084286,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["622397"],"award-info":[{"award-number":["622397"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Graduiertenkolleg 1763 (QuantLA)"],"award-info":[{"award-number":["Graduiertenkolleg 1763 (QuantLA)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["681988"],"award-info":[{"award-number":["681988"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["771005"],"award-info":[{"award-number":["771005"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universal-algebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky--Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite $\\omega$-categorical structures; moreover, by a recent result of Hubi\u010dka and Ne\u0161et\u0159il, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property.<\/jats:p>","DOI":"10.1137\/19m128466x","type":"journal-article","created":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T10:32:51Z","timestamp":1629455571000},"page":"1359-1409","source":"Crossref","is-referenced-by-count":8,"title":["A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP"],"prefix":"10.1137","volume":"50","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florent","family":"Madelaine","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3517-1745","authenticated-orcid":true,"given":"Antoine","family":"Mottet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,8,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"L. Barto, M. Kompatscher, M. Ol\u0161\u00e1k, T. V. Pham, and M. Pinsker,\n                      The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems\n                      , in Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS'17), 2017; also available online fromhttps:\/\/arxiv.org\/abs\/1612.07551.","DOI":"10.1109\/LICS.2017.8005128"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(1:7)2012"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"L. Barto and M. Pinsker,\n                      The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems\n                      , in Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science (LICS'16), 2016, pp. 615-622,https:\/\/arxiv.org\/abs\/1602.04353.","DOI":"10.1145\/2933575.2934544"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/18M1216213"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"atypb7","unstructured":"M. Bodirsky,\n                      Complexity classification in infinite-domain constraint satisfaction\n                      . M\u00e9moire d'habilitation \u00e0 diriger des recherches, Universit\u00e9 Diderot-Paris 7,https:\/\/arxiv.org\/abs\/1201.0856, 2012."},{"key":"atypb8","unstructured":"M. Bodirsky,\n                      Ramsey classes: Examples and constructions\n                      , in Surveys in Combinatorics. London Math. Soc. Lecture Note Ser. 424, Cambridge University Press, Cambridge, 2015,https:\/\/arxiv.org\/abs\/1502.05146."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.05.012"},{"key":"atypb10","first-page":"10","volume":"16","author":"Bodirsky M.","year":"2020","journal-title":"Log. Methods Comput. Sci."},{"key":"atypb11","first-page":"8","author":"Bodirsky M.","year":"2012","journal-title":"Log. Methods Comput. Sci."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5260"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and A. Mottet,\n                      Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction\n                      , in Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science (LICS'16), 2016, pp. 623-632; preprint available athttps:\/\/arxiv.org\/abs\/1601.04520.","DOI":"10.1145\/2933575.2934515"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Bodirsky, A. Mottet, M. Ols\u00e1k, J. Oprsal, M. Pinsker, and R. Willard,\n                      Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)\n                      , in Proceedings of the 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2019), Vancouver, BC, Canada, June 24-27, 2019, IEEE, 2019, pp. 1-12.","DOI":"10.1109\/LICS.2019.8785883"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8179"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"atypb17","unstructured":"M. Bodirsky and M. Pinsker,\n                      Canonical Functions: A Proof via Topological Dynamics\n                      , preprint,https:\/\/arxiv.org\/abs\/1610.09660, 2016."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2019.23"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.028"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov,\n                      A dichotomy theorem for nonuniform CSPs\n                      , in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, 2017, pp. 319-330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"atypb21","unstructured":"A. A. Bulatov and P. Jeavons,\n                      Algebraic Structures in Combinatorial Problems\n                      . Technical report MATH-AL-4-2001, Technische Universit\u00e4t Dresden, 2001."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"P. J. Cameron,\n                      Oligomorphic Permutation Groups\n                      , Cambridge University Press, Cambridge, 1990.","DOI":"10.1017\/CBO9780511549809"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"A. K. Chandra and P. M. Merlin,\n                      Optimal implementation of conjunctive queries in relational data bases\n                      , in Proceedings of the Symposium on Theory of Computing (STOC), 1977, pp. 77-90.","DOI":"10.1145\/800105.803397"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0641"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"T. Feder and M. Y. Vardi,\n                      Monotone monadic SNP and constraint satisfaction\n                      , in Proceedings of the Symposium on Theory of Computing (STOC), 1993, pp. 612-622.","DOI":"10.1145\/167088.167245"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"atypb28","first-page":"311","author":"Feder T.","year":"2003","journal-title":"Proceedings of LICS"},{"key":"atypb29","unstructured":"C. Feier, A. Kuusisto, and C. Lutz,\n                      Rewritability in monadic disjunctive datalog, MMSNP, and expressive description logics (invited talk)\n                      , in Proceedings of the 20th International Conference on Database Theory (ICDT 2017), M. Benedikt and G. Orsi, eds., Leibniz International Proceedings in Informatics (LIPIcs) 68, Dagstuhl, Germany, 2017, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 1:1-1:17,http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7063."},{"key":"atypb30","unstructured":"C. Feier, C. Lutz, and A. Kuusisto,\n                      Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics\n                      , in Proceedings of the 20th International Conference on Database Theory (ICDT17), 2017."},{"key":"atypb31","first-page":"241","author":"Hubi\u010dka J.","year":"2015","journal-title":"Berlin"},{"key":"atypb32","unstructured":"J. Hubi\u010dka and J. Ne\u0161et\u0159il,\n                      All Those Ramsey Classes (Ramsey Classes with Closures and Forbidden Homomorphisms)\n                      , also available online fromhttps:\/\/arxiv.org\/abs\/1606.07979v2, 2016."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0503-1"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2405-4"},{"key":"atypb35","first-page":"3","author":"Larose B.","year":"2007","journal-title":"Log. Methods Comput. Sci."},{"key":"atypb36","unstructured":"C. Lutz and L. Sabellek,\n                      A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL\n                      ,https:\/\/arxiv.org\/abs\/1904.12533, 2019."},{"key":"atypb37","unstructured":"C. Lutz and F. Wolter,\n                      On the relationship between consistent query answering and constraint satisfaction problems\n                      , in Proceedings of the 18th International Conference on Database Theory (ICDT15), 2015."},{"key":"atypb38","unstructured":"F. Madelaine,\n                      Constraint Satisfaction Problems and Related Logic\n                      , Ph.D thesis, University of Leicester, 2003."},{"key":"atypb39","first-page":"5","author":"Madelaine F.","year":"2009","journal-title":"Log. Methods Comput. Sci."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/050634840"},{"key":"atypb41","first-page":"345","author":"Madelaine F. R.","year":"2010","journal-title":"Proceedings of CP"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"D. Zhuk,\n                      A proof of CSP dichotomy conjecture\n                      , in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, 2017, pp. 331-342.","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M128466X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:18:28Z","timestamp":1787339908000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M128466X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M128466X"],"URL":"https:\/\/doi.org\/10.1137\/19m128466x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}