{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:37Z","timestamp":1759063597536,"version":"3.41.2"},"reference-count":26,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2010,10,27]],"date-time":"2010-10-27T00:00:00Z","timestamp":1288137600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"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(G), the constraint satisfaction problem with global cardinality constraints that allows only relations from the set G. The main result of this paper characterizes sets G that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.<\/jats:p>","DOI":"10.2168\/lmcs-6(4:4)2010","type":"journal-article","created":{"date-parts":[[2010,11,26]],"date-time":"2010-11-26T21:56:28Z","timestamp":1290808588000},"source":"Crossref","is-referenced-by-count":8,"title":["The complexity of global cardinality constraints"],"prefix":"10.46298","volume":"Volume 6, Issue 4","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2010,10,27]]},"reference":[{"key":"10.2168\/LMCS-6(4:4)2010_Baker75:chinese-remainder","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187059"},{"key":"10.2168\/LMCS-6(4:4)2010_Barto08:graphs","doi-asserted-by":"crossref","unstructured":"Libor Barto, Marcin Kozik, and Todd Niven. Graphs, polymorphisms and the complexity of homomorphism problems. InSTOC, pages 789-796, 2008.","DOI":"10.1145\/1374376.1374488"},{"key":"10.2168\/LMCS-6(4:4)2010_Bodnarchuk69:Galua1","first-page":"1","volume":"3","author":"V.G. Bodnarchuk, L.A. Kaluzhnin, V.N. Ko","year":"1969","journal-title":"Kibernetika"},{"key":"10.2168\/LMCS-6(4:4)2010_Bourdais03:hibiscus","doi-asserted-by":"crossref","unstructured":"St\u00e9phane Bourdais, Philippe Galinier, and Gilles Pesant. Hibiscus: A constraint programming application to staff scheduling in health care. InCP, pages 153-167, 2003.","DOI":"10.1007\/978-3-540-45193-8_11"},{"key":"10.2168\/LMCS-6(4:4)2010_Bulatov03:conservative","doi-asserted-by":"crossref","unstructured":"A.A. Bulatov. Tractable conservative constraint satisfaction problems. InLICS, pages 321-330, 2003.","DOI":"10.1109\/LICS.2003.1210072"},{"key":"10.2168\/LMCS-6(4:4)2010_Bulatov06:3-element","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"10.2168\/LMCS-6(4:4)2010_Bulatov06:simple","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"10.2168\/LMCS-6(4:4)2010_Bulatov07:towards","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"10.2168\/LMCS-6(4:4)2010_Bulatov05:classifying","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"10.2168\/LMCS-6(4:4)2010_DBLP:journals\/jcss\/ChenK03","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.09.003"},{"key":"10.2168\/LMCS-6(4:4)2010_Cooper89:kconsistency","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90080-5"},{"key":"10.2168\/LMCS-6(4:4)2010_Creignou08:cardinality","doi-asserted-by":"crossref","unstructured":"Nadia Creignou, Henning Schnoor, and Ilka Schnoor. Non-uniform boolean constraint satisfaction problems with cardinality constraint. InCSL, pages 109-123, 2008.","DOI":"10.1007\/978-3-540-87531-4_10"},{"key":"10.2168\/LMCS-6(4:4)2010_Denecke-Wismath02","doi-asserted-by":"crossref","unstructured":"K. Denecke and S.L. Wismath.Universal algebra and applications in Theoretical Computer Science. Chapman and Hall\/CRC Press, 2002.","DOI":"10.1201\/9781315273686"},{"key":"10.2168\/LMCS-6(4:4)2010_Feder98:monotone","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"10.2168\/LMCS-6(4:4)2010_Geiger68:closed","doi-asserted-by":"crossref","unstructured":"D. Geiger. Closed systems of function and predicates.Pacific Journal of Mathematics, pages 95-100, 1968.","DOI":"10.2140\/pjm.1968.27.95"},{"key":"10.2168\/LMCS-6(4:4)2010_Gottlob01:hypertree","doi-asserted-by":"crossref","unstructured":"G. Gottlob, L. Leone, and F. Scarcello. Hypertree decompositions: A survey. InMFCS, volume 2136 ofLNCS, pages 37-57. Springer-Verlag, 2001.","DOI":"10.1007\/3-540-44683-4_5"},{"key":"10.2168\/LMCS-6(4:4)2010_Grohe07:other-side","doi-asserted-by":"crossref","unstructured":"Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side.J. ACM, 54(1), 2007.","DOI":"10.1145\/1206035.1206036"},{"key":"10.2168\/LMCS-6(4:4)2010_Grohe06:fractional","doi-asserted-by":"crossref","unstructured":"Martin Grohe and D\u00e1niel Marx. Constraint solving via fractional edge covers. InSODA, pages 289-298, 2006.","DOI":"10.1145\/1109557.1109590"},{"key":"10.2168\/LMCS-6(4:4)2010_Idziak07:tractability","doi-asserted-by":"crossref","unstructured":"P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, and R. Willard. Tractability and learnability arising from algebras with few subpowers. InProceedings of the 22th Annual IEEE Simposium on {Logic in Computer Science}. IEEE Computer Society, 2007.","DOI":"10.1109\/LICS.2007.50"},{"key":"10.2168\/LMCS-6(4:4)2010_Jeavons98:consist","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00022-8"},{"key":"10.2168\/LMCS-6(4:4)2010_Jeavons97:closure","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"10.2168\/LMCS-6(4:4)2010_Jeavons99:expressive","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009890709297"},{"issue":"2","key":"10.2168\/LMCS-6(4:4)2010_Marx05:parametrized","first-page":"153","volume":"14","author":"D\u00e1niel Marx","year":"2005","journal-title":"Computational Complexity Special issue ``Conference on Computational Complexity (CCC) 2004.''"},{"key":"10.2168\/LMCS-6(4:4)2010_Quimper04:cardinality","doi-asserted-by":"crossref","unstructured":"Claude-Guy Quimper, Alejandro L\u00f3pez-Ortiz, Peter van Beek, and Alexander Golynski. Improved algorithms for the global cardinality constraint. InCP, pages 542-556, 2004.","DOI":"10.1007\/978-3-540-30201-8_40"},{"key":"10.2168\/LMCS-6(4:4)2010_Gomes04:cardinality","doi-asserted-by":"crossref","unstructured":"Jean-Charles R\u00e9gin and Carla P. Gomes. The cardinality matrix constraint. InCP, pages 572-587, 2004.","DOI":"10.1007\/978-3-540-30201-8_42"},{"key":"10.2168\/LMCS-6(4:4)2010_Rosenberg98:hyperstructures","doi-asserted-by":"crossref","unstructured":"I.G. Rosenberg. Multiple-valued hyperstructures. InProceedings of the 28th International Symposium on Multiple-Valued Logic (ISMVL '98), pages 326-333, 1998.","DOI":"10.1109\/ISMVL.1998.679509"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1025\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1025\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T07:00:52Z","timestamp":1740726052000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,27]]},"references-count":26,"URL":"https:\/\/doi.org\/10.2168\/lmcs-6(4:4)2010","relation":{"is-same-as":[{"id-type":"arxiv","id":"1010.0201","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1010.0201","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2010,10,27]]},"article-number":"1025"}}