Joint work with Michael Pinsker. Let B be a fixed relational structure (e.g. a graph). The Constraint Satisfaction Problem for B, CSP(B), is the computational problem of, given a finite structure A in the same language, deciding whether there is a homomorphism from A into B. Many natural problems in computational complexity can be framed in this fashion. When the structure B is finite, we know that CSP(B) is always in NP, and, assuming P!=NP, we know that whether this problem is in P or NP-complete can be characterised in terms of identities satisfied by the polymorphisms of B (a higher arity generalisation of homomorphisms) (Bulatov 2017, Zhuk 2017).
We are interested in generalising the tools used to study constraint satisfaction problems for finite structures to some infinite structures with many symmetries (finitely bounded homogeneous structures). Since understanding the polymorphisms of B is essential to understand the computational complexity of CSP(B), it is often helpful to find polymorphisms of low arity behaving in some non-trivial way. For this reason, we study what are called the minimal polymorphisms above the automorphism group of B. We carry out a classification of the types of minimal operations which may appear over an arbitrary permutation group G\acts B, generalising the work of Rosenberg (1986) for the trivial group and of Bodirsky and Chen (2007) for oligomorphic permutation groups. This allows us to answer some open problems mentioned by Bodirsky (2021) in his book on infinite domain CSPs.