Binary symmetries of tractable non-rigid structures

We study constraint satisfaction problems of non-rigid structures in a finite and omega-categorical setting. We show that not having a binary essential polymorphism is a sufficient criterion for NP-hardness of the constraint satisfaction problem of a (model-complete) core, as long as its automorphism group is not the free action of a Boolean group. To understand the behaviour of low arity polymorphisms, we classify the possible types of minimal operations above an arbitrary permutation group. In this, we generalise a classical theorem of Rosenberg above the trivial group, and significantly improve a result of Bodirsky and Chen above the automorphism groups of omega-categorical structures. Finally, we answer three questions of Bodirsky on binary polymorphisms of infinite templates for constraint satisfaction problems.