{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T08:05:13Z","timestamp":1762761913846,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T00:00:00Z","timestamp":1649203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004564","name":"Ministry of Education, Science and Technological Development of the Republic of Serbia","doi-asserted-by":"crossref","award":["451-03-68\/2002-14\/200125"],"award-info":[{"award-number":["451-03-68\/2002-14\/200125"]}],"id":[{"id":"10.13039\/501100004564","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Royal Society University Research Fellowship"},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["714532"],"award-info":[{"award-number":["714532"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{QCSP}(\\mathrm{H}) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            when\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{H} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{H}_1,\\ldots ,\\mathrm{H}_n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            so that there exists an edge from every vertex of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{H}_i \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            to every vertex of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{H}_j \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            if and only if\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( i\\lt j \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . We prove that if\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{H} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            has both its initial and final strongly connected component (possibly equal) of size 1, then\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{QCSP}(\\mathrm{H}) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathsf {NL} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and otherwise\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{QCSP}(\\mathrm{H}) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathsf {NP} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -hard.\n          <\/jats:p>","DOI":"10.1145\/3508069","type":"journal-article","created":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T09:59:28Z","timestamp":1649239168000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["QCSP on Reflexive Tournaments"],"prefix":"10.1145","volume":"23","author":[{"given":"Beno\u00eet","family":"Larose","sequence":"first","affiliation":[{"name":"LACIM, Universit\u00e9 du Qu\u00e9bec a Montr\u00e9al, Montr\u00e9al, Qu\u00e9bec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4642-8614","authenticated-orcid":false,"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petar","family":"Markovi\u0107","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Informatics, University of Novi Sad, Novi Sad, Serbia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siani","family":"Smith","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,4,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"J\u00f8rgen Bang-Jensen Pavol Hell and Gary MacGillivray. 1988. The complexity of colouring by semicomplete digraphs. SIAM J. Discr. Math. 1 3 (1988) 281\u2013298.","DOI":"10.1137\/0401029"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Manuel Bodirsky Jan K\u00e1ra and Barnaby Martin. 2012. The complexity of surjective homomorphism problems - a survey. Discr. Appl. Math. 160 12 (2012) 1680\u20131690.","DOI":"10.1016\/j.dam.2012.03.029"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","unstructured":"Ferdinand B\u00f6rner Andrei A. Bulatov Hubie Chen Peter Jeavons and Andrei A. Krokhin. 2009. The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207 9 (2009) 923\u2013944.","DOI":"10.1016\/j.ic.2009.05.003"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917) 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov Peter Jeavons and Andrei A. Krokhin. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34 3 (2005) 720\u2013742.","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_7_2","unstructured":"Paul Camion. 1959. Chemins et circuits hamiltoniens de graphes complets. Compt. Rend. Acad. Sci. Paris 249 (1959) 2151\u20132152."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/060668572"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Hubie Chen Florent R. Madelaine and Barnaby Martin. 2015. Quantified constraints and containment problems. Logic. Methods Comput. Sci. 11 3 (2015).","DOI":"10.2168\/LMCS-11(3:9)2015"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"V\u00edctor Dalmau and Andrei A. Krokhin. 2008. Majority constraints have bounded pathwidth duality. Eur. J. Combin. 29 4 (2008) 821\u2013837.","DOI":"10.1016\/j.ejc.2007.11.020"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3007899"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","unstructured":"Tom\u00e1s Feder and Moshe Y. Vardi. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28 1 (1998) 57\u2013104.","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Petr A. Golovach Dani\u00ebl Paulusma and Jian Song. 2012. Computing vertex-surjective homomorphisms to partially reflexive trees. Theor. Comput. Sci. 457 (2012) 86\u2013100.","DOI":"10.1016\/j.tcs.2012.06.039"},{"key":"e_1_3_2_14_2","unstructured":"P. G. Kolaitis and M. Y. Vardi. 2005. Finite Model Theory and Its Applications Texts in Theoretical Computer Science. Springer-Verlag New York Inc."},{"key":"e_1_3_2_15_2","unstructured":"Benoit Larose. 2006. Taylor operations on finite reflexive structures. Int. J. Math. Comput. Sci. 1 1 (2006) 1\u201326."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3282431"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Benoit Larose and L\u00e1szl\u00f3 Z\u00e1dori. 2005. Finite posets and topological spaces in locally finite varieties. Algebr. Universal. 52 2 (2005) 119\u2013136.","DOI":"10.1007\/s00012-004-1819-7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23786-7_42"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/11780342_36"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","unstructured":"Narayan Vikas. 2013. Algorithms for partition of some class of graphs under compaction and vertex-compaction. Algorithmica 67 2 (2013) 180\u2013206.","DOI":"10.1007\/s00453-012-9720-9"},{"key":"e_1_3_2_21_2","unstructured":"Narayan Vikas. 2017. Computational complexity of graph partition under vertex-compaction to an irreflexive hexagon. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917) 69:1\u201369:14."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.06.024"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470632"},{"key":"e_1_3_2_24_2","unstructured":"Dmitriy Zhuk. No-rainbow problem and the surjective constraint satisfaction problem. arXiv:2003.11764. Retrieved from https:\/\/arxiv.org\/abs\/2003.11764."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384232"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508069","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:29Z","timestamp":1750191149000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,6]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3508069"],"URL":"https:\/\/doi.org\/10.1145\/3508069","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2022,4,6]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}