{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T10:28:35Z","timestamp":1772447315132,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the European Community's Seventh Framework Programme","award":["257039"],"award-info":[{"award-number":["257039"]}]},{"name":"APART fellowship of the Austrian Academy of Sciences as well as through project I836-N23 of the Austrian Science Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,6,30]]},"abstract":"<jats:p>\n            Schaefer's theorem is a complexity classification result for so-called\n            <jats:italic>Boolean constraint satisfaction problems<\/jats:italic>\n            : it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in polynomial time, or is NP-complete.\n          <\/jats:p>\n          <jats:p>\n            We present an analog of this dichotomy result for the\n            <jats:italic>propositional logic of graphs<\/jats:italic>\n            instead of Boolean logic. In this generalization of Schaefer's result, the input consists of a set\n            <jats:italic>W<\/jats:italic>\n            of variables and a conjunction \u03a6 of statements (\u201cconstraints\u201d) about these variables in the language of graphs, where each statement is taken from a fixed finite set \u03a8 of allowed quantifier-free first-order formulas; the question is whether \u03a6 is satisfiable in a graph.\n          <\/jats:p>\n          <jats:p>We prove that either \u03a8 is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. This is achieved by a universal-algebraic approach, which in turn allows us to use structural Ramsey theory. To apply the universal-algebraic approach, we formulate the computational problems under consideration as constraint satisfaction problems (CSPs) whose templates are first-order definable in the countably infinite random graph. Our method for classifying the computational complexity of those CSPs is based on a Ramsey-theoretic analysis of functions acting on the random graph, and we develop general tools suitable for such an analysis which are of independent mathematical interest.<\/jats:p>","DOI":"10.1145\/2764899","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T14:04:16Z","timestamp":1436191456000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Schaefer's Theorem for Graphs"],"prefix":"10.1145","volume":"62","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"TU Dresden, Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Pinsker","sequence":"additional","affiliation":[{"name":"TU Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273534"},{"key":"e_1_2_1_2_1","unstructured":"M. Bodirsky. 2012. Complexity classification in infinite-domain constraint satisfaction. M\u00e9moire d'habilitation \u00e0 diriger des recherches Universit\u00e9 Diderot -- Paris 7. arXiv:1201.0856.  M. Bodirsky. 2012. Complexity classification in infinite-domain constraint satisfaction. M\u00e9moire d'habilitation \u00e0 diriger des recherches Universit\u00e9 Diderot -- Paris 7. arXiv:1201.0856."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.050"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1286198146"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exr011"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and M. Pinsker. 2011a. Reducts of Ramsey structures. AMS Contemp. Math. 558 (Model Theoretic Methods in Finite Combinatorics) 489--519.  M. Bodirsky and M. Pinsker. 2011a. Reducts of Ramsey structures. AMS Contemp. Math. 558 (Model Theoretic Methods in Finite Combinatorics) 489--519.","DOI":"10.1090\/conm\/558\/11058"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993724"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1042-y"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"key":"e_1_2_1_14_1","volume-title":"Proc. LMS. To appear. (Preprint arXiv:1309","author":"Bodirsky M."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60406-5_32"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8268-2_15"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189056.1189076"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355485"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-004-5899-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130113"},{"key":"e_1_2_1_23_1","unstructured":"M. Garey and D. Johnson. 1978. A Guide to NP-Completeness. CSLI Press Stanford.  M. Garey and D. Johnson. 1978. A Guide to NP-Completeness. CSLI Press Stanford."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2100-2"},{"key":"e_1_2_1_25_1","volume-title":"A Shorter Model Theory","author":"Hodges W."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_27_1","unstructured":"J. Ne\u0161et\u0159ril. 1995. Ramsey theory. Handbook of Combinatorics 1331--1403.   J. Ne\u0161et\u0159ril. 1995. Ramsey theory. Handbook of Combinatorics 1331--1403."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90055-9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_30_1","unstructured":"\u00c1. Szendrei. 1986. Clones in Universal Algebra. S\u00e9minaire de Math\u00e9matiques Sup\u00e9rieures. Les Presses de l'Universit\u00e9 de Montr\u00e9al.  \u00c1. Szendrei. 1986. Clones in Universal Algebra. S\u00e9minaire de Math\u00e9matiques Sup\u00e9rieures. Les Presses de l'Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274912"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00061-5"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI). 628--633","author":"Westphal M."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2764899","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2764899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:23Z","timestamp":1750227143000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2764899"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2764899"],"URL":"https:\/\/doi.org\/10.1145\/2764899","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}