72 citations · 368 across the 79 of their papers we have counts for
3 papers · 2 filters
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…
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…