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

lmcs:1025 - Logical Methods in Computer Science, October 27, 2010, Volume 6, Issue 4
The complexity of global cardinality constraints

Authors: Bulatov, Andrei A. and Marx, Daniel

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.


Source : oai:arXiv.org:1010.0201
DOI : 10.2168/LMCS-6(4:4)2010
Volume: Volume 6, Issue 4
Published on: October 27, 2010
Submitted on: June 25, 2015
Keywords: Computer Science - Logic in Computer Science,F.2.2, F.4.1


Share

Browsing statistics

This page has been seen 14 times.
This article's PDF has been downloaded 4 times.