78 citations · 97 across the 5 of their papers we have counts for
3 papers · 1 filter
Algebraic approach to promise constraint satisfaction
Libor Barto, Jakub Bulín, Andrei Krokhin +1
The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) h…
A finer reduction of constraint problems to digraphs
Jakub Bulín, Dejan Delic, Marcel Jackson +1
It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph…
On the reduction of the CSP dichotomy conjecture to digraphs
Jakub Bulin, Dejan Delic, Marcel Jackson +1
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a re…