{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T22:00:30Z","timestamp":1771020030938,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language, that is, a set of relations that are allowed to be used as constraints. A principal research direction aims to distinguish those constraint languages that give rise to tractable CSPs from those that do not.<\/jats:p>\n          <jats:p>\n            We achieve this goal for the important version of the CSP, in which the set of values for each individual variable can be restricted arbitrarily. Restrictions of this type can be studied by considering those constraint languages which contain all possible unary constraints; we call such languages\n            <jats:italic>conservative<\/jats:italic>\n            . We completely characterize conservative constraint languages that give rise to polynomial time solvable CSP classes. In particular, this result allows us to obtain a complete description of those (directed) graphs\n            <jats:italic>H<\/jats:italic>\n            for which the List\n            <jats:italic>H<\/jats:italic>\n            -Coloring problem is solvable in polynomial time. The result, the solving algorithm, and the proofs heavily use the algebraic approach to CSP developed in Jeavons et al. [1997], Jeavons [1998], Bulatov et al. [2005], and Bulatov and Jeavons [2001b, 2003].\n          <\/jats:p>","DOI":"10.1145\/1970398.1970400","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":94,"title":["Complexity of conservative constraint satisfaction problems"],"prefix":"10.1145","volume":"12","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[{"name":"Simon Fraser University, British Columbia, Canada"}]}],"member":"320","published-online":{"date-parts":[[2011,7,22]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187059"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103436748"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652168"},{"key":"e_1_2_2_4_1","unstructured":"Bulatov A. 2002b. Mal'tsev constraints are tractable. Tech. rep. PRG-RR-02-05. Computing Laboratory University of Oxford Oxford U.K.  Bulatov A. 2002b. Mal'tsev constraints are tractable. Tech. rep. PRG-RR-02-05. Computing Laboratory University of Oxford Oxford U.K."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2004.07.044"},{"key":"e_1_2_2_6_1","unstructured":"Bulatov A. and Jeavons P. 2000. Tractable constraints closed under a binary operation. Tech. rep. PRG-TR-12-00. Computing Laboratory University of Oxford Oxford U.K.  Bulatov A. and Jeavons P. 2000. Tractable constraints closed under a binary operation. Tech. rep. PRG-TR-12-00. Computing Laboratory University of Oxford Oxford U.K."},{"key":"e_1_2_2_7_1","unstructured":"Bulatov A. and Jeavons P. 2001a. Algebraic approach to multi-sorted constraints. Tech. rep. PRG-RR-01-18. Computing Laboratory University of Oxford Oxford U.K.  Bulatov A. and Jeavons P. 2001a. Algebraic approach to multi-sorted constraints. Tech. rep. PRG-RR-01-18. Computing Laboratory University of Oxford Oxford U.K."},{"key":"e_1_2_2_8_1","unstructured":"Bulatov A. and Jeavons P. 2001b. Algebraic structures in combinatorial problems. Tech. rep. MATH-AL-4-2001. Technische Universit\u00e4t Dresden Dresden Germany. http:\/\/web.comlab.ox.ac.uk\/oucl\/research\/areas\/constraints\/publications\/index.html.  Bulatov A. and Jeavons P. 2001b. Algebraic structures in combinatorial problems. Tech. rep. MATH-AL-4-2001. Technische Universit\u00e4t Dresden Dresden Germany. http:\/\/web.comlab.ox.ac.uk\/oucl\/research\/areas\/constraints\/publications\/index.html."},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming. 197--202","author":"Bulatov A."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380868"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of 33rd IEEE International Symposium on Multiple-Valued Logic. 343--351","author":"Bulatov A."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90021-3"},{"key":"e_1_2_2_16_1","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications","volume":"7","author":"Creignou N."},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 6th International Symposium on Artificial Intelligence and Mathematics.","author":"Dalmau V.","year":"2000"},{"key":"e_1_2_2_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages and Programming","author":"Dalmau V."},{"key":"e_1_2_2_19_1","unstructured":"Dechter R. 2003. Constraint processing. Morgan Kaufmann San Francisco CA.   Dechter R. 2003. Constraint processing. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_2_20_1","unstructured":"Denecke K. and Wismath S. 2002. Universal Algebra and Applications in Theoretical Computer Science. Chapman and Hall\/CRC Press Boca Raton FL.   Denecke K. and Wismath S. 2002. Universal Algebra and Applications in Theoretical Computer Science. Chapman and Hall\/CRC Press Boca Raton FL."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4%3C260::AID-RSA5%3E3.0.CO;2-W"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Feder T. and Hell P. 2003. Restricted list constraints and list partitions. Unpublished manuscript.  Feder T. and Hell P. 2003. Restricted list constraints and list partitions. Unpublished manuscript.","DOI":"10.1137\/S0895480100384055"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v42:1"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00009-1"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00022-8"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018941030227"},{"key":"e_1_2_2_34_1","series-title":"Lecture Notes in Pure and Applied Mathematics","volume-title":"Logic and Algebra","author":"Kearnes K."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1630659.1630939"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 17th National (U.S.) Conference on Artificial Intelligence. 175--181","author":"Kolaitis P."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90150-3"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-007-2012-6"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"e_1_2_2_41_1","unstructured":"Pippenger N. 1997. Theories of Computability. Cambridge University Press Cambridge U.K.   Pippenger N. 1997. Theories of Computability. Cambridge University Press Cambridge U.K."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"P\u00f6schel R. and Kalu\u017enin L. 1979. Funktionen- und Relationenalgebren. DVW Berlin Germany.  P\u00f6schel R. and Kalu\u017enin L. 1979. Funktionen- und Relationenalgebren. DVW Berlin Germany.","DOI":"10.1007\/978-3-0348-5547-1"},{"key":"e_1_2_2_43_1","article-title":"The Two-Valued Iterative Systems of Mathematical Logic","volume":"5","author":"Post E.","year":"1941","journal-title":"Annals of Mathematical Studies"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_2_45_1","volume-title":"Seminaires de Mathematiques Superieures","volume":"99","author":"Szendrei A.","year":"1986"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970398.1970400","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1970398.1970400","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:53Z","timestamp":1750243973000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970398.1970400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1970398.1970400"],"URL":"https:\/\/doi.org\/10.1145\/1970398.1970400","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2003-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}