3 papers
cs.LO2026
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…
cs.CC2025
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. Th…
cs.LO2024
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…