Algebra Seminar talk
2025-12-05
Nicolas Fassl
Simple Algorithms on finite domain constraint satisfaction problems
Abstract:
For a relational structure A, the constraint satisfaction problem CSP(A) associated with it describes a common computational problem, where the problem consists of assigning values to variables, while obeying given constraints. In this work, we explore three simple algorithms for finite domain CSPs and their algebraic properties. In particular, we find that the arc-consistency algorithm solves a CSP if and only if it has width 1, which is equivalent to the existence of a set polymorphism. The strict width l algorithm can be applied if and only if we find an (l+1) near-unanimity polymorphism, and the basic linear programming relaxation is applicable if and only if we can find totally symmetric polymorphisms of every arity.