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

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

Bibliographic References

10 Documents citing this article

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, https://arxiv.org/abs/1901.07107.

Hubie Chen;Matt Valeriote;Yuichi Yoshida, 2019, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, BIROn (Birkbeck, University of London), 48, 3, pp. 1022-1045, 10.1137/18m121085x, https://eprints.bbk.ac.uk/id/eprint/27754/1/main.pdf.

Joshua Brakensiek;Sivakanth Gopi;Venkatesan Guruswami, arXiv (Cornell University), CSPs with global modular constraints: algorithms and hardness via polynomial representations, 2019, Phoenix AZ USA, 10.1145/3313276.3316401, https://arxiv.org/abs/1902.04740.

Michał Wrona, 2019, The Complexity of Minimal Inference Problem for Conservative Constraint Languages, ACM Transactions on Computational Logic, 20, 2, pp. 1-35, 10.1145/3301410.

Catarina Carvalho;Andrei Krokhin, 2016, On algebras with many symmetric operations, University of Hertfordshire Research Archive (University of Hertfordshire), 26, 05, pp. 1019-1031, 10.1142/s0218196716500429, https://hdl.handle.net/2299/19798.

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, arXiv (Cornell University), Testing Assignments to Constraint Satisfaction Problems, 78, pp. 525-534, 2016, New Brunswick, NJ, USA, 10.1109/focs.2016.63, https://arxiv.org/abs/1608.03017.

Andrei A. Bulatov;Dániel Marx, 2014, Constraint Satisfaction Parameterized by Solution Size, arXiv (Cornell University), 43, 2, pp. 573-616, 10.1137/120882160, https://arxiv.org/abs/1206.4854.

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, https://doi.org/10.1016/j.tcs.2012.12.025.

Manuel Bodirsky;Jan Kára;Barnaby Martin, 2012, The complexity of surjective homomorphism problems—a survey, Discrete Applied Mathematics, 160, 12, pp. 1680-1690, 10.1016/j.dam.2012.03.029, https://doi.org/10.1016/j.dam.2012.03.029.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1528 times.

This article's PDF has been downloaded 327 times.