The complexity of global cardinality constraints

Andrei A. Bulatov; Daniel Marx

doi:10.2168/LMCS-6(4:4)2010

Andrei A. Bulatov ; Daniel Marx - The complexity of global cardinality constraints

lmcs:1025 - Logical Methods in Computer Science, October 27, 2010, Volume 6, Issue 4 - https://doi.org/10.2168/LMCS-6(4:4)2010

The complexity of global cardinality constraintsArticle

Authors: Andrei A. Bulatov ; Daniel Marx

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.

https://doi.org/10.2168/LMCS-6(4:4)2010

Source: arXiv.org:1010.0201

Volume: Volume 6, Issue 4

Secondary volumes: Selected Papers of the 24th IEEE Symposium on Logic in Computer Science (LICS 2009)

Published on: October 27, 2010

Imported on: January 31, 2010

Keywords: Computer Science - Logic in Computer Science, F.2.2, F.4.1

Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

11 Documents citing this article

Hubie Chen, 2024, Algebraic Global Gadgetry for Surjective Constraint Satisfaction, Computational Complexity, 33, 1, 10.1007/s00037-024-00253-4, http://dx.doi.org/10.1007/s00037-024-00253-4.

Gregor Matl;Stanislav Živný, 2020, Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs, arXiv (Cornell University), 82, 12, pp. 3492-3520, 10.1007/s00453-020-00735-1, http://arxiv.org/abs/1901.07107.

Hubie Chen;Matt Valeriote;Yuichi Yoshida, 2019, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, SIAM Journal on Computing, 48, 3, pp. 1022-1045, 10.1137/18m121085x.

Joshua Brakensiek;Sivakanth Gopi;Venkatesan Guruswami, 2019, CSPs with global modular constraints: algorithms and hardness via polynomial representations, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 590-601, 10.1145/3313276.3316401.

Michał Wrona, 2019, The Complexity of Minimal Inference Problem for Conservative Constraint Languages, Jagiellonian University Repository (Jagiellonian University), 20, 2, pp. 1-35, 10.1145/3301410, https://ruj.uj.edu.pl/xmlui/handle/item/72612.

Catarina Carvalho;Andrei Krokhin, 2016, On algebras with many symmetric operations, arXiv (Cornell University), 26, 05, pp. 1019-1031, 10.1142/s0218196716500429, http://arxiv.org/abs/1406.5061.

David A. Cohen;Peter G. Jeavons, 2016, The power of propagation: when GAC is enough, Constraints, 22, 1, pp. 3-23, 10.1007/s10601-016-9251-0, https://doi.org/10.1007/s10601-016-9251-0.

Hubie Chen;Matt Valeriote;Yuichi Yoshida, 2016, Testing Assignments to Constraint Satisfaction Problems, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 525-534, 10.1109/focs.2016.63.

Andrei A. Bulatov;Dániel Marx, 2014, Constraint Satisfaction Parameterized by Solution Size, SIAM Journal on Computing, 43, 2, pp. 573-616, 10.1137/120882160.

Gary MacGillivray;Jacobus Swarts, 2013, Weak near-unanimity functions and digraph homomorphism problems, Theoretical Computer Science, 477, pp. 32-47, 10.1016/j.tcs.2012.12.025.

Manuel Bodirsky;Jan Kára;Barnaby Martin, 2012, The complexity of surjective homomorphism problems—a survey, arXiv (Cornell University), 160, 12, pp. 1680-1690, 10.1016/j.dam.2012.03.029, http://arxiv.org/abs/1104.5257.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3484 times.

This article's PDF has been downloaded 559 times.