19 papers
The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
Manuel Bodirsky, Moritz Jahn, Simon Knäuer +2
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the ne…
Structures preserved by primitive actions of
Manuel Bodirsky, Bertalan Bodor
We present a dichotomy for structures that are preserved by primitive actions of : such a structure primitively positively constructs all finite…
The complexity of finding coset-generating polymorphisms and the promise metaproblem
Manuel Bodirsky, Armin WeiÃ
We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whe…
Symmetric Linear Arc Monadic Datalog and Gadget Reductions
Manuel Bodirsky, Florian Starke
A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three D…
Graph Homomorphisms and Universal Algebra
Manuel Bodirsky
Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational co…
Conservative Maltsev Constraint Satisfaction Problems
Manuel Bodirsky, Andrew Moorhead
One of the central open problems to classify the computational complexity of finite-domain constraint satisfaction problems within P is to prove better algorithmic results for CSPs…