ALCOMFT-TR-03-56

D. Cohen, M. Cooper, P. Jeavons and A. Krokhin
Identifying efficiently solvable cases of non-Boolean Max CSP
Warwick. Work package 4. October 2003.

Abstract: In this paper we study algorithmic approaches to the maximum constraint satisfaction problem (Max CSP) over an arbitrary finite domain. We describe a novel connection between this problem and the supermodular function maximization problem (which is dual to the submodular function minimization problem (SFM)). Using this connection, we are able to identify large classes of efficiently solvable subproblems of Max CSP arising from certain restrictions on the constraint types. Until now, the only known %characterizations of polynomial-time solvable cases for this form of optimization problem were restricted to constraints over a 2-valued (Boolean) domain. Here we obtain the first examples of general families of efficiently solvable cases of Max CSP for arbitrary finite domains, by considering supermodular functions on finite lattices. In addition, for some special cases of supermodular functions, we are able to design algorithms with much tighter complexity bounds than the general SFM algorithm. 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.

keywords: maximum constraint satisfaction, optimization, complexity, algorithms, supermodularity, finite lattice

Postscript file: ALCOMFT-TR-03-56.ps.gz (135 kb).