Showing cs.LOShow all
2 papers · 1 filter
cs.LO2025
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Johanna Brunar, Marcin Kozik, Tomáš Nagy +1
Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative template…
cs.LO2024
Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality
Tomáš Nagy, Michael Pinsker
We investigate the `local consistency implies global consistency' principle of strict width among structures within the scope of the Bodirsky-Pinsker dichotomy conjecture for infin…