19 citations · 81 across the 20 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2016★ 1 cited
All or nothing: toward a promise problem dichotomy for constraint problems
Lucy Ham, Marcel Jackson
A finite constraint language is a finite set of relations over some finite domain . We show that intractability of the constraint satisfaction problem $\operatorna…
cs.CC2014★ 19 cited
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…
cs.CC2013
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…