78 citations · 97 across the 5 of their papers we have counts for
6 papers
The Smallest Hard Trees
Manuel Bodirsky, Jakub Bulín, Florian Starke +1
We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientat…
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…
Deciding absorption in relational structures
Libor Barto, Jakub Bulín
We prove that for finite, finitely related algebras the concepts of an absorbing subuniverse and a Jónsson absorbing subuniverse coincide. Consequently, it is decidable whether a g…
On the complexity of -coloring for special oriented trees
Jakub Bulín
For a fixed digraph , the -coloring problem is the problem of deciding whether a given input digraph admits a homomorphism to . The CSP…
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…