{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:22:05Z","timestamp":1787322125070,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101071674"],"award-info":[{"award-number":["101071674"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For a fixed finite set of finite tournaments [Formula: see text], the [Formula: see text] -free orientation problem asks whether a given finite undirected graph [Formula: see text] has an [Formula: see text] -free orientation, i.e., whether the edges of [Formula: see text] can be oriented so that the resulting digraph does not embed any of the tournaments from [Formula: see text]. We prove that for every [Formula: see text] this problem is in P or NP-complete. Our proof reduces the classification task to a complete complexity classification of the orientation completion problem for [Formula: see text], which is the variant of the problem above where the input is a directed graph instead of an undirected graph, introduced by Bang-Jensen, Huang, and Zhu [ J. Graph Theory, 87 (2018), pp. 285\u2013304]. Our proof uses results from the theory of constraint satisfaction and a result of Agarwal and Kompatscher [ J. Symb. Log., 83 (2018),\u00a0 pp. 395\u2013415] about infinite permutation groups and transformation monoids.<\/jats:p>","DOI":"10.1137\/23m1604849","type":"journal-article","created":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T04:08:21Z","timestamp":1736482101000},"page":"170-205","source":"Crossref","is-referenced-by-count":2,"title":["Forbidden Tournaments and the Orientation Completion Problem"],"prefix":"10.1137","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":true,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Fakult\u00e4t Mathematik, Institut f\u00fcr Algebra, TU Dresden, 01069 Dresden."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santiago","family":"Guzm\u00e1n-Pro","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t Mathematik, Institut f\u00fcr Algebra, TU Dresden, 01069 Dresden."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,1,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2017.74"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.11.001"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1069"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22157"},{"key":"ref5","unstructured":"A. Barsukov, On Dichotomy Above Feder and Vardi\u2019s Logic, Ph.D. thesis, \u00c9cole Doctorale Science pour l\u2019Eng\u00e9nieur, Clermont-Ferrand, 2022."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061319500107"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"L. Barto and M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, in Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science \u2013 LICS\u201916, 2016, pp. 615\u2013622.","DOI":"10.1145\/2933575.2934544"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2661643"},{"key":"ref10","unstructured":"Z. Bitter and A. Mottet, Generalized completion problems with forbidden tournaments, in 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Leibniz International Proceedings in Informatics (LIPIcs) 306, R. Kr\u00e1lovi\u010d and A. Ku\u010dera, eds. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2024, pp. 28:1\u201328:17, https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2024.28."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1017\/9781107337534"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and B. Bodor, Canonical polymorphisms of Ramsey structures and the unique interpolation property, in Proceedings of the Symposium on Logic in Computer Science (LICS), 2021.","DOI":"10.1109\/LICS52264.2021.9470683"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"M. Bodirsky, S. Kn\u00e4uer, and F. Starke, ASNP: A tame fragment of existential second-order logic, in Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy - Lecture Notes in Comput. Sci. 12098, M. Anselmo, G. D. Vedova, F. Manea, and A. Pauly, eds. Springer, 2020, pp. 149\u2013162, https:\/\/doi.org\/10.1007\/978-3-030-51466-2.","DOI":"10.1007\/978-3-030-51466-2_13"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/19M128466X"},{"key":"ref15","first-page":"1","volume":"14","author":"Bodirsky M.","year":"2018","journal-title":"Log. Methods Comput. Sci."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1042-y"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2019.23"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-020-0647-8"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2017, Berkeley, CA, 2017, pp. 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46908-4_25"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070304"},{"key":"ref25","first-page":"125","volume":"9","author":"Erd\u0151s P.","year":"1964","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia, Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"ref27","unstructured":"R. Feller and M. Pinsker, An Algebraic Proof of the Dichotomy for Graph Orientation Problems with Forbidden Tournaments, preprint, https:\/\/arxiv.org\/abs\/2405.20263, 2024."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/0118004"},{"key":"ref29","first-page":"115","volume-title":"Theory of Graphs","author":"Gallai T.","year":"1968"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"ref31","unstructured":"S. Guzm\u00e1n-Pro. Local Expressions of Hereditary Classes, Ph.D. thesis, Facultad de Ciencias, UNAM, 2023, http:\/\/132.248.9.195\/ptd2023\/marzo\/0837271\/Index.html."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2022.127555"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2024.128912"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19650280503"},{"key":"ref35","volume-title":"A Shorter Model Theory","author":"Hodges W.","year":"1997"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2405-4"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"A. Mottet and M. Pinsker, Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures, 71 (2024), pp. 1\u201347, https:\/\/doi.org\/10.1145\/3689207.","DOI":"10.1145\/3689207"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2021.6"},{"key":"ref39","unstructured":"C. Paul and E. Protopapas, Tree-Layout Based Graph Classes: Proper Chordal Graphs, in 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Dagstuhl, Germany, 2024, pp. 55:1\u201355:18, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2024.55."},{"key":"ref40","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic","volume":"5","author":"Post E. L.","year":"1941"},{"key":"ref41","first-page":"129","volume":"1","author":"Roy B.","year":"1967","journal-title":"Rev. Fr. Inform. Rech. Oper."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060307"},{"key":"ref43","first-page":"758","volume":"147","author":"Vitaver L. M.","year":"1962","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"D. N. Zhuk, A proof of the CSP dichotomy conjecture, in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS, Berkeley, CA, 2017, pp. 331\u2013342.","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1604849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:25Z","timestamp":1787318305000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1604849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,10]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1137\/23M1604849"],"URL":"https:\/\/doi.org\/10.1137\/23m1604849","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,10]]}}}