{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:47Z","timestamp":1787340467991,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"National Research, Development and Innovation Fund of Hungary"},{"name":"The New National Excellence Program Bolyai+ of the Ministry of Human Capacities"},{"DOI":"10.13039\/501100003825","name":"Hungarian Academy of Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["18-20123S"],"award-info":[{"award-number":["18-20123S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P27600"],"award-info":[{"award-number":["P27600"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"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\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","award":["EFOP-3.6.2-16-2017-00015"],"award-info":[{"award-number":["EFOP-3.6.2-16-2017-00015"]}],"id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["257039"],"award-info":[{"award-number":["257039"]}],"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":["681988"],"award-info":[{"award-number":["681988"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["K109185"],"award-info":[{"award-number":["K109185"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>For $n\\geq 3$, let $(H_n, E)$ denote the $n$th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on $n$ vertices. We show that for all structures $\\Gamma$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\\Gamma$ either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.<\/jats:p>","DOI":"10.1137\/16m1082974","type":"journal-article","created":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T11:08:35Z","timestamp":1563448115000},"page":"1224-1264","source":"Crossref","is-referenced-by-count":23,"title":["Constraint Satisfaction Problems for Reducts of Homogeneous Graphs"],"prefix":"10.1137","volume":"48","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4727-918X","authenticated-orcid":true,"given":"Michael","family":"Pinsker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e1s","family":"Pongr\u00e1cz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,7,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.050"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/3105907"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"L. Barto, M. Kompatscher, M. Ol\u0161\u00e1k, M. Pinsker, and T. V. Pham,\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, IEEE, Washington, DC, 2017,https:\/\/doi.org\/10.1109\/LICS.2017.8005128.","DOI":"10.1109\/LICS.2017.8005128"},{"key":"atypb8","first-page":"623","author":"Bodirsky M.","year":"2016","journal-title":"Washington, DC"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/3154832"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"atypb12","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; preprint,https:\/\/arxiv.org\/abs\/1201.0856, 2012."},{"key":"atypb13","first-page":"489","author":"Bodirsky M.","year":"2011","journal-title":"RI"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1042-y"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/2764899"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"key":"atypb17","first-page":"615","author":"Barto L.","year":"2016","journal-title":"Washington, DC"},{"key":"atypb18","unstructured":"M. Bodirsky and M. Pinsker,\n                      Canonical Functions: A Proof via Topological Dynamics\n                      , preprint,https:\/\/arxiv.org\/abs\/1610.09660, 2016."},{"key":"atypb19","unstructured":"L. Barto and M. Pinsker,\n                      Topology is Irrelevant\n                      , preprint, available fromhttp:\/\/www.karlin.mff.cuni.cz\/ barto\/Articles\/pinsker_topologyirrelevant.pdf, 2018."},{"key":"atypb20","unstructured":"M. Bodirsky, M. Pinsker, and A. Pongr\u00e1cz,\n                      Projective clone homomorphisms\n                      , J. Symbolic Logic, to appear,https:\/\/doi.org\/10.1017\/jsl.2019.23; preprint,https:\/\/arxiv.org\/abs\/1409.4601, 2014."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.2178\/jsl.7804020"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov,\n                      A dichotomy theorem for nonuniform CSPs\n                      , in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, 2017, pp. 319-330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"atypb24","first-page":"122","author":"Bodirsky M.","year":"2012","journal-title":"Germany"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan,\n                      Complexity Classifications of Boolean Constraint Satisfaction Problems\n                      , SIAM Monogr. Discrete Math. Appl. 7, SIAM, Philadelphia, 2001,https:\/\/doi.org\/10.1137\/1.9780898718546.","DOI":"10.1137\/1.9780898718546"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2100-2"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1994-054-1"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0503-1"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1980-0583847-2"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90097-6"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2017.01.009"},{"key":"atypb35","unstructured":"E. L. Post,\n                      The Two-Valued Iterative Systems of Mathematical Logic\n                      , Ann. Math. Stud. 5, Princeton University Press, Princeton, NJ, 1941."},{"key":"atypb36","first-page":"216","author":"Schaefer T. J.","year":"1978","journal-title":"New York"},{"key":"atypb37","unstructured":"\u00c1. Szendrei,\n                      Clones in Universal Algebra\n                      , S\u00e9minaire de Math\u00e9matiques Sup\u00e9rieures, Les Presses de l'Universit\u00e9 de Montr\u00e9al, Montreal, Canada, 1986."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.2307\/2274912"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"K. Tent and M. Ziegler,\n                      A Course in Model Theory\n                      , Lecture Notes in Logic 40, Cambridge University Press, Cambridge, UK, 2012.","DOI":"10.1017\/CBO9781139015417"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"D. Zhuk,\n                      A proof of CSP dichotomy conjecture\n                      , in Proceedings of the 58th Annual IEEE 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\/16M1082974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:43Z","timestamp":1787337343000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1082974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/16M1082974"],"URL":"https:\/\/doi.org\/10.1137\/16m1082974","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}