# Binarisation via Dualisation for Valued Constraints

@inproceedings{Cohen2015BinarisationVD, title={Binarisation via Dualisation for Valued Constraints}, author={David A. Cohen and Martin C. Cooper and Peter Jeavons and Stanislav Živn{\'y}}, booktitle={AAAI}, year={2015} }

Constraint programming is a natural paradigm for many combinatorial optimisation problems. The complexity of constraint satisfaction for various forms of constraints has been widely-studied, both to inform the choice of appropriate algorithms, and to understand better the boundary between polynomial-time complexity and NP-hardness.
In constraint programming it is well-known that any constraint satisfaction problem can be converted to an equivalent binary problem using the so-called dual… Expand

#### Topics from this paper

#### 6 Citations

The Power of Sherali-Adams Relaxations for General-Valued CSPs

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

A precise algebraic characterization of the power of Sherali--Adams relaxations for solvability of valued constraint satisfaction problems (CSPs) to optimality is given and a dichotomy theorem for valued constraint languages that can express an injective unary function is obtained. Expand

Binarisation for Valued Constraint Satisfaction Problems

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2017

It is established that VCSPs over a fixed valued constraint language are polynomial-time equivalent to Minimum-Cost Homomorphism Problems over aFixed digraph. Expand

Complexity of Infinite-Domain Constraint Satisfaction

- Computer Science
- 2021

This monograph presents a self-contained introduction to the universal-algebraic approach to complexity classification, treating both finite and infinite-domain CSPs. Expand

O ct 2 01 5 Necessary Conditions for Tractability of Valued CSPs ∗

- 2018

The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SICOMP’13]… Expand

A Model-Theoretic View on Qualitative Constraint Reasoning

- Computer Science, Mathematics
- J. Artif. Intell. Res.
- 2017

A model-theoretic perspective on qualitative constraint reasoning is presented and the significance of omega-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms are discussed. Expand

Graph Homomorphisms and Universal Algebra Course Notes

- 2015

1 The Basics 2 1.1 Graphs and Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Graph Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 The… Expand

#### References

SHOWING 1-10 OF 34 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 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

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

Binary vs. non-binary constraints

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

A formal comparison of the dual transformation and the hidden transformation of constraint satisfaction problems with finite domains focuses on two backtracking algorithms that maintain a local consistency property at each node in their search tree: the forward checking and maintaining arc consistency algorithms. Expand

On digraph coloring problems and treewidth duality

- Mathematics, Computer Science
- 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05)
- 2005

It is known that every constraint satisfaction problem (CSP) reduces, and is in fact polynomially equivalent, to a digraph coloring problem, and it is shown that it is semi-decidable, given H, whether the H-coloring problem is definable in full first-order logic. 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

The Expressive Power of Binary Submodular Functions

- Computer Science
- MFCS
- 2009

The results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Expand

On the Reduction of the CSP Dichotomy Conjecture to Digraphs

- Mathematics, Computer Science
- CP
- 2013

A simple variant of such a reduction is presented and used to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. Expand

A finer reduction of constraint problems to digraphs

- Mathematics, Computer Science
- Log. Methods Comput. Sci.
- 2015

The Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs. Expand

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

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

This paper isolates a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit a dichotomy, and explains the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. Expand