Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov’s proof of the dichotomy for conservative templates, and the structural dichotomy for smooth digraphs of algebraic length 1 due to Barto, Kozik, and Niven. We lift the combined scenario to the infinite, and prove that any smooth digraph of algebraic length 1 pp-constructs, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, every finite structure – and hence its conservative graph-colouring problem is NP-hard – unless the digraph has a pseudo-loop, i.e. an edge within an orbit. We thereby overcome, for the first time, previous obstacles to lifting structural results for digraphs in this context from finite to ω-categorical structures; the strongest lifting results hitherto not going beyond a genera-lisation of the Hell-Nešetřil theorem for undirected graphs. As a consequence, we obtain a new algebraic invariant of arbitrary ω-categorical structures enriched by pairs of orbits which fail to pp-construct some finite structure.

We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC'11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP'16) on graph satisfiability.

Abstract. We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities [Formula: see text]) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain constraint satisfaction problems (CSPs) studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of Monotone Monadic SNP (MMSNP) sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al. In particular, the bounded width hierarchy collapses in those cases as well. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures and show the applicability of infinite-domain CSPs to other fields.

We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n ≥ 3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al.. In particular, the bounded width hierarchy collapses in those cases as well.