Skip to main content

Research Repository

Advanced Search

Supermodular functions and the complexity of MAX CSP

Cohen, D.; Cooper, M.; Jeavons, P.; Krokhin, A.

Authors

D. Cohen

M. Cooper

P. Jeavons



Abstract

In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. Using the theory of sub- and supermodular functions on finite lattice-ordered sets, we obtain the first examples of general families of efficiently solvable cases of MAX CSP for arbitrary finite domains. In addition, we provide the first dichotomy result for a special class of non-Boolean MAX CSP, by considering binary constraints given by supermodular functions on a totally ordered set. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of MAX CSP which are hard even to approximate.

Citation

Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics, 149(1-3), 53-72. https://doi.org/10.1016/j.dam.2005.03.003

Journal Article Type Article
Publication Date Aug 1, 2005
Deposit Date Feb 21, 2008
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 149
Issue 1-3
Pages 53-72
DOI https://doi.org/10.1016/j.dam.2005.03.003
Keywords Constraint satisfaction problem, Optimization, Supermodularity.