78 citations · 116 across the 14 of their papers we have counts for
17 papers
Functors on relational structures which admit both left and right adjoints
Víctor Dalmau, Andrei Krokhin, Jakub Opršal
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors and between thin categories of relational s…
An invitation to the promise constraint satisfaction problem
Andrei Krokhin, Jakub Opršal
The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. Afte…
Topology and adjunction in promise constraint satisfaction
Andrei Krokhin, Jakub Opršal, Marcin Wrochna +1
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a -colouring of a graph that is promised to be -colourable, where $c\g…
The complexity of 3-colouring -colourable graphs
Andrei Krokhin, Jakub Opršal
We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph , the -colouring problem is to decide whether a given gra…
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…
On the hardness of losing weight
Andrei Krokhin, Dániel Marx
We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, an…