72 citations · 368 across the 79 of their papers we have counts for
5 papers · 1 filter
Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets
Manuel Bodirsky, Dugald Macpherson, Johan Thapper
A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved…
The Complexity of Rooted Phylogeny Problems
Manuel Bodirsky, Jens K Mueller
Several computational problems in phylogenetic reconstruction can be formulated as restrictions of the following general problem: given a formula in conjunctive normal form where t…
Reducts of Ramsey structures
Manuel Bodirsky, Michael Pinsker
One way of studying a relational structure is to investigate functions which are related to that structure and which leave certain aspects of the structure invariant. Examples are…
The Complexity of Surjective Homomorphism Problems -- a Survey
Manuel Bodirsky, Jan Kara, Barnaby Martin
We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction…
Tractable Set Constraints
Manuel Bodirsky, Martin Hils, Alex Krimkevich
Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set c…