77 citations · 733 across the 54 of their papers we have counts for
7 papers · 1 filter
The limits of SDP relaxations for general-valued CSPs
Johan Thapper, Stanislav Zivny
It has been shown that for a general-valued constraint language the following statements are equivalent: (1) any instance of can be solved to optimalit…
Functional Clones and Expressibility of Partition Functions
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum +2
We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions ) closed under (essentially) multiplication, summati…
Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +1
The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variab…
Binarisation for Valued Constraint Satisfaction Problems
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +3
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the alge…
The power of Sherali-Adams relaxations for general-valued CSPs
Johan Thapper, Stanislav Zivny
We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is th…
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
Martin C. Cooper, Stanislav Živný
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding pa…
On Planar Valued CSPs
Peter Fulla, Stanislav Zivny
We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. First, we show that in…