# The complexity of soft constraint satisfaction

@article{Cohen2006TheCO, title={The complexity of soft constraint satisfaction}, author={David A. Cohen and Martin C. Cooper and Peter Jeavons and Andrei A. Krokhin}, journal={Artif. Intell.}, year={2006}, volume={170}, pages={983-1016} }

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of constraints to a corresponding set of algebraic operations, known as polymorphisms. In this paper we extend the analysis of complexity to the more general framework of combinatorial optimisation problems expressed using various… Expand

#### 140 Citations

An Algebraic Characterisation of Complexity for Valued Constraint

- Mathematics, Computer Science
- CP
- 2006

It is shown that the existence of a non-trivial fractional polymorphism is a necessary condition for the tractability of a valued constraint language with rational or infinite costs over any finite domain (assuming P ≠ NP). Expand

The Constraint Satisfaction Problem: Complexity and Approximability

- Computer Science, Mathematics
- The Constraint Satisfaction Problem
- 2017

This report documents the material presented during the course of the Dagstuhl Seminar 18231 “The Constraint Satisfaction Problem: Complexity and Approximability”, aimed at bringing together researchers using all the different techniques in the study of the CSP to share their insights obtained. Expand

Approximability of Integer Programming with Generalised Constraints

- Mathematics, Computer Science
- CP
- 2006

A complete classification for the approximability of all maximal constraint languages, and a complete classification of the approxIMability of the problem when the set of allowed constraints contains all permutation constraints are presented. Expand

An Algebraic Theory of Complexity for Discrete Optimization

- Mathematics, Computer Science
- SIAM J. Comput.
- 2013

It is shown that the complexity of a finite-domain discrete optimization problem is determined by certain algebraic properties of the objective function, which are called weighted polymorphisms, and this approach is used to derive a complete classification of complexity for the Boolean case. Expand

MAX ONES GENERALISED TO LARGER DOMAINS

- 2006

We study a family of problems, called Maximum Solution, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of… Expand

An Algebraic Approach to Valued Constraint Satisfaction

- Mathematics, Computer Science
- CSL
- 2017

A notion of polymorphism is introduced that captures the pp-definability in the style of Geiger’s result, and sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Expand

Combinatorial Optimization Algorithms via Polymorphisms

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 2015

This work designs a randomized algorithm to minimize a function f that admits a fractional polymorphism which is measure preserving and has a transitive symmetry in the value-oracle model. Expand

Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains

- Mathematics, Computer Science
- ArXiv
- 2013

In this paper we study the computational complexity of the (extended) minimum cost homomorphism problem (Min-Cost-Hom) as a function of a constraint language, i.e. a set of constraint relations and… Expand

Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains

- Computer Science
- STACS
- 2014

In this paper we study the computational complexity of the extended minimum cost homomorphism problem (Min-Cost-Hom) as a function of a constraint language, i.e. a set of constraint relations and… Expand

The Power of Linear Programming for Valued CSPs

- Mathematics, Computer Science
- 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
- 2012

This work obtains tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: sub modular on arbitrary lattices, bisubmodular on arbitrary finite domains, and weakly (and hence strongly) tree-sub modular on arbitrarily trees. Expand

#### References

SHOWING 1-10 OF 72 REFERENCES

Classifying the Complexity of Constraints Using Finite Algebras

- Mathematics, Computer Science
- SIAM J. Comput.
- 2005

It is shown that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra is explored. Expand

The complexity of maximal constraint languages

- Mathematics, Computer Science
- STOC '01
- 2001

This paper systematically study the complexity of all maximal constraint languages, that is, languages whose expressive power is just weaker than that of the language of all constraints. Expand

A dichotomy theorem for constraints on a three-element set

- Mathematics, Computer Science
- The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
- 2002

Every subclass of the CSP defined by a set of allowed constraints is either tractable or NP-complete, and the criterion separating them is that conjectured by Bulatov et al. (2001). Expand

Constraints and universal algebra

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2004

It is shown that a constraint satisfaction problem instance can be viewed as a pair of relational structures, and the solutions to the problem are then the structure preserving mappings between these two relational structures. Expand

Closure properties of constraints

- Mathematics, Computer Science
- JACM
- 1997

This paper investigates the subclasses that arise from restricting the possible constraint types, and shows that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. Expand

A Maximal Tractable Class of Soft Constraints

- Computer Science, Mathematics
- IJCAI
- 2003

This paper identifies a class of soft binary constraints for which the problem of finding the optimal solution is tractable, and shows that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. Expand

A dichotomy theorem for constraint satisfaction problems on a 3-element set

- Mathematics, Computer Science
- JACM
- 2006

Every subproblem of the CSP is either tractable or NP-complete, and the criterion separating them is that conjectured in Bulatov et al. Expand

How to Determine the Expressive Power of Constraints

- Mathematics, Computer Science
- Constraints
- 2004

It is shown that indicator problems provide a simple method to test for tractability and the expressive power of a given set of constraint types is determined by certain algebraic properties of the underlying relations. Expand

The Approximability of Constraint Satisfaction Problems

- Mathematics, Computer Science
- SIAM J. Comput.
- 2000

Tight bounds on the "approximability" of every problem in Max Ones, Min CSP, and Min Ones are determined and this completely classifies all optimization problems derived from Boolean constraint satisfaction. Expand

Fast Parallel Constraint Satisfaction

- Mathematics, Computer Science
- Artif. Intell.
- 1993

It is shown here that a CSP with this type of constraint relations (and no restrictions on its graph) can be solved by an efficient (i.e., with polynomial time complexity) sequential algorithm. Expand