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.


    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

    10 Documents citing this article

    Consultation statistics

    This page has been seen 1206 times.
    This article's PDF has been downloaded 286 times.