{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:33Z","timestamp":1750307373809,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"9","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"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":["Commun. ACM"],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a certain value. We study the complexity of the problem CCSP(\u0393), the CSP with global cardinality constraints that allows only relations from the set \u0393. The main result of this paper characterizes sets \u0393 that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.<\/jats:p>","DOI":"10.1145\/1810891.1810914","type":"journal-article","created":{"date-parts":[[2010,8,31]],"date-time":"2010-08-31T13:05:55Z","timestamp":1283259955000},"page":"99-106","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Constraint satisfaction problems and global cardinality constraints"],"prefix":"10.1145","volume":"53","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[{"name":"Simon Fraser Univerity, Burnaby, BC, Canada"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"volume-title":"Benjamin Cummihgs","year":"1994","author":"Allen J.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.11.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.34"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_63"},{"volume-title":"AAAI","year":"2004","author":"Bessi\u00e8re C.","key":"e_1_2_1_6_1"},{"volume-title":"LICS","year":"2003","author":"Bulatov A.","key":"e_1_2_1_7_1"},{"volume-title":"ISMVL","year":"2003","author":"Bulatov A.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_2_1_11_1","unstructured":"Bulatov A.A. Marx D. Constraint satisfaction parameterized by solution size. Manuscript.  Bulatov A.A. Marx D. Constraint satisfaction parameterized by solution size. Manuscript."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.38"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87531-4_10"},{"volume-title":"Constraint Processing","year":"2003","author":"Dechter R.","key":"e_1_2_1_15_1"},{"volume-title":"Universal Algebra and Applications in Theoretical Computer Science","year":"2002","author":"Denecke K.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/359642.359654"},{"volume-title":"Proceedings of AAAI-90","year":"1990","author":"Freuder E.C.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"volume-title":"ECAI","year":"1992","author":"Kautz H.A.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"volume-title":"Parameterized complexity and kernelizability of Max Ones and Exact Ones problems. Submitted","year":"2010","author":"Kratsch S.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"volume-title":"ICALP","year":"2007","author":"Larose B.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0195-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806790"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(94)00080-U"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90011-L"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1810891.1810914","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1810891.1810914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:23:01Z","timestamp":1750245781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1810891.1810914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":34,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1810891.1810914"],"URL":"https:\/\/doi.org\/10.1145\/1810891.1810914","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2010,9]]},"assertion":[{"value":"2010-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}