# An Algebraic Characterisation of Complexity for Valued Constraint

@inproceedings{Cohen2006AnAC, title={An Algebraic Characterisation of Complexity for Valued Constraint}, author={David A. Cohen and Martin C. Cooper and Peter Jeavons}, booktitle={CP}, year={2006} }

Classical constraint satisfaction is concerned with the feasibility of satisfying a collection of constraints. The extension of this framework to include optimisation is now also being investigated and a theory of so-called soft constraints is being developed. In this extended framework, tuples of values allowed by constraints are given desirability weightings, or costs, and the goal is to find the most desirable (or least cost) assignment.
The complexity of any optimisation problem depends… Expand

#### Topics from this paper

#### 51 Citations

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection

- Mathematics, Computer Science
- MFCS
- 2011

It is shown that when the costs are non-negative rational numbers or infinite, then the complexity of a valued constraint problem is determined by certain algebraic properties of this valued constraint language, which are called weighted polymorphisms. Expand

A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs

- Computer Science, Mathematics
- ArXiv
- 2015

This paper adapts a recent proof to the more general setting of VCSP to show that each VCSP with a fixed finite (valued) constraint language is equivalent to one where the constraint language contains a single binary relation (i.e. a digraph) and one finite-valued unary function. Expand

The power of linear programming for valued CSPs: a constructive characterization

- Mathematics, Computer Science
- ArXiv
- 2012

It is proved that if BLP solves the language then the language admits a binary commutative fractional polymorphism and that core languages that do not satisfy the authors' condition are NP-hard. Expand

The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization

- Mathematics, Computer Science
- ICALP
- 2013

It is proved that if BLP solves the language then the language admits a binary commutative fractional polymorphism and that core languages that do not satisfy the authors' condition are NP-hard. 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

The Complexity of General-Valued CSPs

- Computer Science, Mathematics
- 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- 2015

It is proved that if a constraint language satisfies this algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language, then the VCSP is tractable. Expand

A dichotomy theorem for conservative general-valued CSPs

- Computer Science, Mathematics
- ArXiv
- 2010

A Schaefer-like dichotomy theorem is proved for the case of so-called conservative languages: if all cost functions in the language satisfy a certain condition then any instance can be solved in polynomial time by the algorithm of Kolmogorov and Zivny, otherwise the language is NP-hard. Expand

Algorithms and Hardness Results for Some Valued CSPs

- Mathematics
- 2009

In the Constraint Satisfaction Problem (CSP) one is supposed to find an assignment to a set of variables so that a set of given constraints are satisfied. Many problems, both practical and… Expand

The complexity of conservative finite-valued CSPs

- Mathematics, Computer Science
- ArXiv
- 2010

An elementary proof of a complete complexity classification of conservative finite-valued languages is given: it is shown that every conservative infinite-valued language is either tractable or NP-hard. 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

#### References

SHOWING 1-10 OF 39 REFERENCES

The complexity of soft constraint satisfaction

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

It is shown that many tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms and the notion of multimorphism is used to give a complete classification of complexity for the Boolean case which extends several earlier classification results for particular special cases. Expand

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 Approximability of Three-valued MAX CSP

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

This paper establishes the first step in this direction by establishing this result for MAX CSP over a three-element domain and presents a simple description of all polynomial-time solvable cases of the problem, which uses the well-known algebraic combinatorial property of supermodularity. Expand

Supermodular functions and the complexity of MAX CSP

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2005

The complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain is studied, and the first examples of general families of efficiently solvable cases of MAX CSP for arbitrary finite domains are obtained. 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

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

Soft Constraints: Complexity and Multimorphisms

- Computer Science
- CP
- 2003

It is shown that a number of maximal tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms. 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

A Complete Characterization of Complexity for Boolean Constraint Optimization Problems

- Computer Science, Mathematics
- CP
- 2004

This work focuses on valued constraints over Boolean variables, and establishes a dichotomy theorem which characterizes the complexity of any problem involving a fixed set of constraints of this kind. Expand