number of equivalent formulations. In this paper, we work with the formulation as the relational homomorphism problem: given two similar relational structures ${\mathbf{A}}$ and ${\mathbf{B}}$, does there exist a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$? In this formulation, one can view each relation of ${\mathbf{A}}$ as containing variable tuples that are constrained together, and the corresponding relation of ${\mathbf{B}}$ as containing the permissible values for the variable tuples [@FederVardi].

The constraint satisfaction problem is in general NP-hard; this general intractability has motivated the study of restricted versions of the CSP that have various desirable complexity and algorithmic properties. A natural and well-studied way to restrict the CSP is to fix the value relations that can be used to pose constraints; in the homomorphism formulation, this corresponds to fixing the right-hand side structure ${\mathbf{B}}$, which is also known as the *constraint language*. Each structure ${\mathbf{B}}$ then gives rise to a problem ${{\mathsf{CSP}}}({\mathbf{B}})$, and one obtains a rich family of problems that include boolean satisfiability problems, graph homomorphism problems, and satisfiability problems on algebraic equations. One of the primary current research threads involving such problems is to understand for which finite-universe constraint languages ${\mathbf{B}}$ the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is polynomial-time tractable [@bulatov-valeriote]; there is 