78 citations · 133 across the 7 of their papers we have counts for
10 papers
A categorical perspective on constraint satisfaction: The wonderland of adjunctions
Maximilian Hadek, Tomáš Jakl, Jakub Opršal
The so-called algebraic approach to the constraint satisfaction problem (CSP) has been a prevalent method of the study of complexity of these problems since early 2000's. The core…
A topological proof of the Hell-Nešetřil dichotomy
Sebastian Meyer, Jakub Opršal
We provide a new proof of a theorem of Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990] using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theor…
Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal +2
A linearly ordered (LO) -colouring of a hypergraph is a colouring of its vertices with colours such that each edge contains a unique maximal colour. Deciding wheth…
Local consistency as a reduction between constraint satisfaction problems
Victor Dalmau, Jakub Opršal
We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions…
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…
Taylor's modularity conjecture and related problems for idempotent varieties
Jakub Opršal
We provide a partial result on Taylor's modularity conjecture, and several related problems. Namely, we show that the interpretability join of two idempotent varieties that are not…
The wonderland of reflections
Libor Barto, Jakub Opršal, Michael Pinsker
A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a fixed template is that pp-interpretations between at most countable ω-categorical rela…