77 citations · 279 across the 13 of their papers we have counts for
14 papers
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…
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…
Constraint Satisfaction and Semilinear Expansions of Addition over the Rationals and the Reals
Peter Jonsson, Johan Thapper
A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals, or the integers. Semilinear relations h…
Tropical Dominating Sets in Vertex-Coloured Graphs
J. -A. Angles d'Auriac, Cs. Bujtas, A. El Maftouhi +7
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating set…
Sherali-Adams relaxations for valued CSPs
Johan Thapper, Stanislav Zivny
We consider Sherali-Adams linear programming relaxations for solving valued constraint satisfaction problems to optimality. The utility of linear programming relaxations in this co…
Necessary conditions for tractability of valued CSPs
Johan Thapper, Stanislav Zivny
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 e…