{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:11:37Z","timestamp":1784110297063,"version":"3.55.0"},"reference-count":92,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T00:00:00Z","timestamp":1626220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme","award":["\u00a0771005 ERC and \u00a0681988"],"award-info":[{"award-number":["\u00a0771005 ERC and \u00a0681988"]}]},{"name":"Austrian Science","award":["P29931 FWF"],"award-info":[{"award-number":["P29931 FWF"]}]},{"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"}]},{"name":"Charles University Research Centre program","award":["UNCE\/SCI\/022 and PRIMUS\/SCI\/12"],"award-info":[{"award-number":["UNCE\/SCI\/022 and PRIMUS\/SCI\/12"]}]},{"name":"UK EPSRC","award":["EP\/R034516\/1"],"award-info":[{"award-number":["EP\/R034516\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a\u00a0fixed constraint language on a\u00a0finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms\u2014high-dimensional symmetries of solution spaces\u2014to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases.<\/jats:p>\n          <jats:p>\n            The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a\u00a0new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a\u00a0fixed constraint language is equivalent to a\u00a0problem of this form. This allows us to identify a\u00a0\u201cmeasure of symmetry\u201d that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness\/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any\n            <jats:italic>k<\/jats:italic>\n            \u2265 3, it is NP-hard to find a\u00a0(2\n            <jats:italic>k<\/jats:italic>\n            -1)-colouring of a\u00a0given\n            <jats:italic>k<\/jats:italic>\n            -colourable graph.\n          <\/jats:p>","DOI":"10.1145\/3457606","type":"journal-article","created":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T16:23:56Z","timestamp":1626279836000},"page":"1-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Algebraic Approach to Promise Constraint Satisfaction"],"prefix":"10.1145","volume":"68","author":[{"given":"Libor","family":"Barto","sequence":"first","affiliation":[{"name":"Charles University, Prague, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"Bul\u00edn","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1245-3456","authenticated-orcid":false,"given":"Jakub","family":"Opr\u0161al","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2016.01.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_5_1","volume-title":"Simplified inapproximability of hypergraph coloring via -agreeing families. (Apr","author":"Austrin Per","year":"2019","unstructured":"Per Austrin , Amey Bhangale , and Aditya Potukuchi . 2019. Simplified inapproximability of hypergraph coloring via -agreeing families. (Apr . 2019 ). arXiv:1904.01163. Per Austrin, Amey Bhangale, and Aditya Potukuchi. 2019. Simplified inapproximability of hypergraph coloring via -agreeing families. (Apr. 2019). arXiv:1904.01163."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381179"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462897"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-2011-087-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3470152.3470169"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330063"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(1:7)2012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_2_1_15_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Andrei Krokhin , and Ross Willard . 2017 . Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.) . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1\u201344. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.1. 10.4230\/DFU.Vol7.15301.1 Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1\u201344. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.1."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1216213"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_2_1_20_1","volume-title":"Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G","author":"Bodirsky Manuel","unstructured":"Manuel Bodirsky . 2008. Constraint satisfaction problems with infinite templates . In Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G . Kolaitis, and Heribert Vollmer (Eds.), Vol. 5250 . Springer , 196\u2013228. DOI:https:\/\/doi.org\/10.1007\/978-3-540-92800-3_8. 10.1007\/978-3-540-92800-3_8 Manuel Bodirsky. 2008. Constraint satisfaction problems with infinite templates. In Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer (Eds.), Vol. 5250. Springer, 196\u2013228. DOI:https:\/\/doi.org\/10.1007\/978-3-540-92800-3_8."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_16"},{"key":"e_1_2_1_22_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Bodirsky Manuel","year":"2017","unstructured":"Manuel Bodirsky and Marcello Mamino . 2017 . Constraint satisfaction problems over numeric domains. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.) . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 79\u2013111. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.79. 10.4230\/DFU.Vol7.15301.79 Manuel Bodirsky and Marcello Mamino. 2017. Constraint satisfaction problems over numeric domains. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 79\u2013111. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.79."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3470152.3470212"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01267873"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982459"},{"key":"e_1_2_1_27_1","volume-title":"Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy. ECCC Report No. 183","author":"Brakensiek Joshua","year":"2016","unstructured":"Joshua Brakensiek and Venkatesan Guruswami . 2016. Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy. ECCC Report No. 183 ( 2016 ). Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2016\/183\/. Joshua Brakensiek and Venkatesan Guruswami. 2016. Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy. ECCC Report No. 183 (2016). Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2016\/183\/."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization Conference: Algorithms and Techniques (APPROX\/RANDOM\u201917)","author":"Brakensiek Joshua","year":"2017","unstructured":"Joshua Brakensiek and Venkatesan Guruswami . 2017 . The quest for strong inapproximability results with perfect completeness . In Proceedings of the Approximation, Randomization, and Combinatorial Optimization Conference: Algorithms and Techniques (APPROX\/RANDOM\u201917) . 4:1\u20134:20. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.4. 10.4230\/LIPIcs.APPROX-RANDOM.2017.4 Joshua Brakensiek and Venkatesan Guruswami. 2017. The quest for strong inapproximability results with perfect completeness. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization Conference: Algorithms and Techniques (APPROX\/RANDOM\u201917). 4:1\u20134:20. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.4."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175422"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310463"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1312745"},{"key":"e_1_2_1_32_1","volume-title":"Combinatorial Optimization Algorithms via Polymorphisms. (Jan","author":"Brown-Cohen Jonah","year":"2015","unstructured":"Jonah Brown-Cohen and Prasad Raghavendra . 2015. Combinatorial Optimization Algorithms via Polymorphisms. (Jan . 2015 ). arXiv:1501.01598. Jonah Brown-Cohen and Prasad Raghavendra. 2015. Combinatorial Optimization Algorithms via Polymorphisms. (Jan. 2015). arXiv:1501.01598."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316300"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134757"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.63"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039708"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.03.003"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/647486.726506"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Ficak Miron","unstructured":"Miron Ficak , Marcin Kozik , Miroslav Ol\u0161\u00e1k , and Szymon Stankiewicz . 2019. Dichotomy for symmetric Boolean PCSPs . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (Leibniz International Proceedings in Informatics (LIPIcs)) , Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.), Vol. 132 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 57:1\u201357:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.57 arXiv:1904.12424. 10.4230\/LIPIcs.ICALP.2019.57 Miron Ficak, Marcin Kozik, Miroslav Ol\u0161\u00e1k, and Szymon Stankiewicz. 2019. Dichotomy for symmetric Boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (Leibniz International Proceedings in Informatics (LIPIcs)), Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.), Vol. 132. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 57:1\u201357:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.57 arXiv:1904.12424."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/140995520"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3383-0"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Guruswami Venkatesan","unstructured":"Venkatesan Guruswami and Sai Sandeep . 2020. -to-1 hardness of coloring 3-colorable graphs with colors . In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Leibniz International Proceedings in Informatics (LIPIcs)) , Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.), Vol. 168 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany , 62:1\u201362:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.62. 10.4230\/LIPIcs.ICALP.2020.62 Venkatesan Guruswami and Sai Sandeep. 2020. -to-1 hardness of coloring 3-colorable graphs with colors. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Leibniz International Proceedings in Informatics (LIPIcs)), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.), Vol. 168. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 62:1\u201362:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.62."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press.  Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_17"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_63_1","article-title":"Coloring 3-colorable graphs with less than  colors","volume":"64","author":"Mikkel Thorup Kawarabayashi","year":"2017","unstructured":"Ken-ichi Kawarabayashi and Mikkel Thorup . 2017 . Coloring 3-colorable graphs with less than colors . J. ACM 64 , 1 (2017), 4:1\u20134:23. DOI:https:\/\/doi.org\/10.1145\/3001582. 10.1145\/3001582 Ken-ichi Kawarabayashi and Mikkel Thorup. 2017. Coloring 3-colorable graphs with less than colors. J. ACM 64, 1 (2017), 4:1\u20134:23. DOI:https:\/\/doi.org\/10.1145\/3001582.","journal-title":"J. ACM"},{"key":"e_1_2_1_64_1","volume-title":"On the hardness of approximating the chromatic number. Combinatorica 20, 3 (01","author":"Khanna Sanjeev","year":"2000","unstructured":"Sanjeev Khanna , Nathan Linial , and Shmuel Safra . 2000. On the hardness of approximating the chromatic number. Combinatorica 20, 3 (01 Mar. 2000 ), 393\u2013415. DOI:https:\/\/doi.org\/10.1007\/s004930070013. 10.1007\/s004930070013 Sanjeev Khanna, Nathan Linial, and Shmuel Safra. 2000. On the hardness of approximating the chromatic number. Combinatorica 20, 3 (01 Mar. 2000), 393\u2013415. DOI:https:\/\/doi.org\/10.1007\/s004930070013."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875607"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_6"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00076"},{"key":"e_1_2_1_69_1","volume-title":"Topology and adjunction in promise constraint satisfaction. (Mar","author":"Krokhin Andrei","year":"2020","unstructured":"Andrei Krokhin , Jakub Opr\u0161al , Marcin Wrochna , and Stanislav \u017divn\u00fd . 2020. Topology and adjunction in promise constraint satisfaction. (Mar . 2020 ). arXiv:2003.11351. Andrei Krokhin, Jakub Opr\u0161al, Marcin Wrochna, and Stanislav \u017divn\u00fd. 2020. Topology and adjunction in promise constraint satisfaction. (Mar. 2020). arXiv:2003.11351."},{"key":"e_1_2_1_70_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Krokhin Andrei","year":"2017","unstructured":"Andrei Krokhin and Stanislav \u017divn\u00fd ( Eds .). 2017 . The Constraint Satisfaction Problem: Complexity and Approximability . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). 2017. The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.07.011"},{"key":"e_1_2_1_73_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Larose Benoit","year":"2017","unstructured":"Benoit Larose . 2017 . Algebra and the complexity of digraph CSPs: A survey. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.) . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 267\u2013285. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.267. 10.4230\/DFU.Vol7.15301.267 Benoit Larose. 2017. Algebra and the complexity of digraph CSPs: A survey. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 267\u2013285. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.267."},{"key":"e_1_2_1_74_1","volume-title":"Bounded width problems and algebras. Algeb. Univers. 56, 3 (01","author":"Larose Benoit","year":"2007","unstructured":"Benoit Larose and L\u00e1szl\u00f3 Z\u00e1dori . 2007. Bounded width problems and algebras. Algeb. Univers. 56, 3 (01 June 2007 ), 439\u2013466. DOI:https:\/\/doi.org\/10.1007\/s00012-007-2012-6. 10.1007\/s00012-007-2012-6 Benoit Larose and L\u00e1szl\u00f3 Z\u00e1dori. 2007. Bounded width problems and algebras. Algeb. Univers. 56, 3 (01 June 2007), 439\u2013466. DOI:https:\/\/doi.org\/10.1007\/s00012-007-2012-6."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000730"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700017122"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12097"},{"key":"e_1_2_1_79_1","unstructured":"Miroslav Ol\u0161\u00e1k. 2018. Personal communication.  Miroslav Ol\u0161\u00e1k. 2018. Personal communication."},{"key":"e_1_2_1_80_1","first-page":"1","article-title":"Loop conditions","volume":"81","author":"Ol\u0161\u00e1k Miroslav","year":"2019","unstructured":"Miroslav Ol\u0161\u00e1k . 2019 . Loop conditions . Algeb. Univers. 81 , 1 (Nov. 2019), 2:1\u20132:11. DOI:https:\/\/doi.org\/10.1007\/s00012-019-0631-3 arXiv:1701.00260. 10.1007\/s00012-019-0631-3 Miroslav Ol\u0161\u00e1k. 2019. Loop conditions. Algeb. Univers. 81, 1 (Nov. 2019), 2:1\u20132:11. DOI:https:\/\/doi.org\/10.1007\/s00012-019-0631-3 arXiv:1701.00260.","journal-title":"Algeb. Univers."},{"key":"e_1_2_1_81_1","volume-title":"Taylor\u2019s modularity conjecture and related problems for idempotent varieties. Order (Nov","author":"Opr\u0161al Jakub","year":"2017","unstructured":"Jakub Opr\u0161al . 2017. Taylor\u2019s modularity conjecture and related problems for idempotent varieties. Order (Nov . 2017 ). DOI:https:\/\/doi.org\/10.1007\/s11083-017-9441-4. 10.1007\/s11083-017-9441-4 Jakub Opr\u0161al. 2017. Taylor\u2019s modularity conjecture and related problems for idempotent varieties. Order (Nov. 2017). DOI:https:\/\/doi.org\/10.1007\/s11083-017-9441-4."},{"key":"e_1_2_1_82_1","unstructured":"Michael Pinsker. 2015. Algebraic and model theoretic methods in constraint satisfaction. (2015). arXiv:1507.00931.  Michael Pinsker. 2015. Algebraic and model theoretic methods in constraint satisfaction. (2015). arXiv:1507.00931."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00297-7"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_87_1","volume-title":"Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26, 3","author":"Schrijver Alexander","year":"1978","unstructured":"Alexander Schrijver . 1978. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26, 3 ( 1978 ), 454\u2013461. Alexander Schrijver. 1978. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26, 3 (1978), 454\u2013461."},{"key":"e_1_2_1_88_1","first-page":"1","article-title":"A strong Mal\u2019cev condition for locally finite varieties omitting the unary type","volume":"64","author":"Siggers Mark H.","year":"2010","unstructured":"Mark H. Siggers . 2010 . A strong Mal\u2019cev condition for locally finite varieties omitting the unary type . Algeb. Univers. 64 , 1 (Oct. 2010), 15\u201320. DOI:https:\/\/doi.org\/10.1007\/s00012-010-0082-3. 10.1007\/s00012-010-0082-3 Mark H. Siggers. 2010. A strong Mal\u2019cev condition for locally finite varieties omitting the unary type. Algeb. Univers. 64, 1 (Oct. 2010), 15\u201320. DOI:https:\/\/doi.org\/10.1007\/s00012-010-0082-3.","journal-title":"Algeb. Univers."},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02945141"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/2974019"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381175"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457606","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:07Z","timestamp":1750195687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,14]]},"references-count":92,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3457606"],"URL":"https:\/\/doi.org\/10.1145\/3457606","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,14]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}