{'fraction_non_alphanumeric': 0.0705473906659531, 'fraction_numerical': 0.01151318046464397, 'mean_word_length': 3.2887241054613936, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 95, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A dichotomy theorem for nonuniform CSPs simplified

In a non-uniform Constraint Satisfaction problem CSP(G), where G is a set of relations on a finite set A, the goal is to find an assignment of values to variables subject to constraints imposed on specified sets of variables using the relations from G. The Dichotomy Conjecture for the non-uniform CSP states that for every constraint language G the problem CSP(G) is either solvable in polynomial time or is NP-complete. It was proposed by Feder and Vardi in their seminal 1993 paper. In this paper we confirm the Dichotomy Conjecture.


Introduction
In a Constraint Satisfaction Problem (CSP) the question is to decide whether or not it is possible to satisfy a given set of constraints. One of the standard ways to specify a constraint is to require that a combination of values of a certain set of variables belongs to a given relation. If the constraints allowed in a problem have to come from some set Γ of relations, such a restricted problem is referred to as a nonuniform CSP and denoted CSP(Γ). The set Γ is then called a constraint language. Nonuniform CSPs not only provide a powerful framework ubiquitous across a wide range of disciplines from theoretical computer science to computer vision, but also admit natural and elegant reformulations such as the homomorphism problem, and characterizations, in particular, as the class of problems equivalent to a logic class MMSNP. Many different versions of the CSP have been studied across various fields. These include CSPs over infinite sets, counting CSPs (and related Holant problem and the problem of computing partition functions), several variants of optimization CSPs, valued CSPs, quantified CSPs, and numerous related problems. The reader is referred to the recent book [50] for a survey of the state-of-the art in some of these areas. In this paper we, however, focus on the decision nonuniform CSP and its complexity.
A systematic study of the complexity of nonuniform CSPs was started by Schaefer in 1978 [58] who showed that for every constraint language Γ over a 2-element set the problem CSP(Γ) is either solvable in polynomial time or is NP-complete. Schaefer also asked about the complexity of CSP(Γ) for languages over larger sets. The next step in the study of nonuniform CSPs was made in the seminal paper by Feder and Vardi [35,36], who apart from considering numerous aspects of the problem, posed the Dichotomy Conjecture that states that for every finite constraint language Γ over a finite set the problem CSP(Γ) is either solvable in polynomial time or is NP-complete. This conjecture has become a focal point of the CSP research and most of the effort in this area revolves to some extent around the Dichotomy Conjecture.
The complexity of the CSP in general and the Dichotomy Conjecture in particular has been studied by several research communities using a variety of methods, each contributing an important aspect of the problem. The CSP has been an established area in artificial intelligence for decades, and apart from developing efficient general methods of solving CSPs researchers tried to identify tractable fragments of the problem [34]. A very important special case of the CSP, the (Di)Graph Homomorphism problem and the H-Coloring problem have been actively studied in the graph theory community, see, e.g. [41,40] and subsequent works by Hell, Feder, Bang-Jensen, Rafiey and others. Homomorphism duality introduced in these works has been very useful in understanding the structure of constraint problems. The CSP plays a major role and has been successfully studied in database theory, logic and model theory [47,48,39], although the version of the problem mostly used there is not necessarily nonuniform. Logic games and strategies are now a standard tool in most of CSP algorithms. An interesting approach to the Dichotomy Conjecture through long codes was suggested by Kun and Szegedy [51]. Brown-Cohen and Raghavendra proposed to study the conjecture using techniques based on decay of correlations [11]. In this paper we use the algebraic structure of the CSP, which is briefly discussed next.
The most effective approach to the study of the CSP turned out to be the algebraic approach that associates every constraint language with its (universal) algebra of polymorphisms. This approach was first developed in a series of papers by Jeavons and coauthors [44,45,46] and then refined by Bulatov, Krokhin, Barto, Kozik, Maroti, Zhuk and others [5,8,6,28,16,30,54,55,60,61]. While the complexity of CSP(Γ) has been already solved for some interesting classes of structures such as graphs [41], the algebraic approach allowed the researchers to confirm the Dichotomy Conjecture in a number of more general cases: for languages over a set of size up to 7 [12,17,53,61], so called conservative languages [14,18,19,3], and some classes of digraphs [7]. It also helped to design the main classes of CSP algorithms [6,27,21,10,43], and to refine the exact complexity of the CSP [1,8,33,52].
In this paper we confirm the Dichotomy Conjecture for arbitrary languages over finite sets. More precisely we prove the following Theorem 1 For any finite constraint language Γ over a finite set the problem CSP(Γ) is either solvable in polynomial time or is NP-complete.
The same result has been independently obtained by Zhuk [62,63,64]. The proved criterion matches the algebraic form of the Dichotomy Conjecture suggested in [28]. The hardness part of the conjecture has been known for long time. Therefore the main achievement of this paper is a polynomial time algorithm for problems satisfying the tractability condition from [28].
Using the algebraic language we can state the result in a stronger form. Let A be a finite idempotent algebra and let CSP(A) denote the union of problems CSP(Γ) such that every term operation of A is a polymorphism of Γ. Problem CSP(A) is no longer a nonuniform CSP, and Theorem 1 allows for problems CSP(Γ) ⊆ CSP(A) to have different solution algorithms even when A meets the tractability condition. We show that the solution algorithm only depends on the algebra A.
Theorem 2 For a finite idempotent algebra that satisfies the conditions of the Dichotomy Conjecture there is a uniform solution algorithm for CSP(A).
An interesting question arising from Theorems 1,2 is known as the Meta-problem: Given a constraint language or a finite algebra, decide whether or not it satisfies the conditions of the theorems. The answer to this question is not quite simple, for a thorough study of the Meta-problem see [32,38].
We start with introducing the terminology and notation for CSPs that is used throughout the paper and reminding the basics of the algebraic approach. Then in Section 4 we introduce the key ingredients used in the algorithm: separation of congruences and centralizers. Then in Section 5 we apply these concepts to CSPs, first, to demonstrate how centralizers help to decompose an instance into smaller subinstances, and, second, to introduce a new kind of minimality condition for CSPs, block minimality. After that we state the main results used by the algorithm and describe the algorithm itself. The last part of the paper, Sections 6-9, is devoted to proving the technical results.

CSP, universal algebra and the Dichotomy conjecture
For a detailed introduction to the CSP and the algebraic approach to its structure the reader is referred to a recent survey by Barto et al. [9]. Basics of universal algebra can be learned from the textbook [31]. In preliminaries to this paper we therefore focus on what is needed for our result.

The CSP
The 'AI' formulation of the CSP best fits our purpose. Fix a finite set A and let Γ be a constraint language over A, that is, a set -not necessarily finite -of relations over A. The (nonuniform) Constraint Satisfaction Problem (CSP) associated with language Γ is the problem CSP(Γ), in which, an instance is a pair (V, C), where V is a set of variables; and C is a set of constraints, i.e. pairs s, R , where s = (v 1 , . . . , v k ) is a tuple of variables from V , the constraint scope, and R ∈ Γ, the k-ary constraint relation. We always assume that relations are given explicitly by a list of tuples. The way constraints are represented does not matter if Γ is finite, but it may change the complexity of the problems for infinite languages. The goal is to find a solution, i.e., a mapping ϕ : V → A such that for every constraint s, R ∈ C, ϕ(s) ∈ R.

Algebraic methods in the CSP
Jeavons et al. in [44,45] were the first to observe that higher order symmetries of constraint languages, called polymorphisms, play a significant role in the study of the complexity of the CSP. A polymorphism of a relation R over A is an operation f (x 1 , . . . , x k ) on A such that for any choice of a 1 , . . . , a k ∈ R we have f (a 1 , . . . , a k ) ∈ R. If this is the case we also say that f preserves R, or that R is invariant with respect to f . A polymorphism of a constraint language Γ is an operation that is a polymorphism of every R ∈ Γ.
Theorem 3 ( [44,45]) For constraint languages Γ, ∆, where Γ is finite, if every polymorphism of ∆ is also a polymorphism of Γ, then CSP(Γ) is polynomial time reducible to CSP(∆). 1 Listed below are several types of polymorphisms that occur frequently throughout the paper. The presence of each of these polymorphisms imposes strong restrictions on the structure of invariant relations that can be used in designing a solution algorithm. Some of such results will be mentioned later.
k-ary near-unanimity operation is a k-ary operation u(x 1 , . . . , x k ) such that u(y, x, . . . , x) = u(x, y, x, . . . , x) = · · · = u(x, . . . , x, y) = x for all x, y ∈ A; a ternary near-unanimity operation m is called a majority operation, it satisfies the equations m(y, x, x) = m(x, y, x) = m(x, x, y) = x; -Mal'tsev operation is a ternary operation h(x, y, z) satisfying the equations h(x, y, y) = h(y, y, x) = x for all x, y ∈ A; the affine operation x − y + z of an Abelian group is a special case of a Mal'tsev operation; -k-ary weak near-unanimity operation is a k-ary operation w that satisfies the same equations as a near-unanimity operation w(y, x, . . . , x) = · · · = w(x, . . . , x, y), except for the last one (= x).
To illustrate the effect of polymorphisms on the structure of invariant relations we give a few examples that involve polymorphisms introduced above. First, we need some terminology and notation.
By [n] we denote the set {1, . . . , n}. For sets A 1 , . . . , A n tuples from A 1 ×· · ·×A n are denoted in boldface, say, a; the ith component of a is referred to as a[i]. An n-ary relation R over sets A 1 , . . . , A n is any subset of A 1 × · · · × A n . For I = {i 1 , . . . , i k } ⊆ [n] by pr I a, pr I R we denote the projections pr I a = (a[i 1 ], . . . , a[i k ]), pr I R = {pr I a | a ∈ R} of tuple a and relation R. If pr i R = A i for each i ∈ [n], relation R is said to be a subdirect product of A 1 ×· · ·×A n . Sometimes it is convenient to label the coordinate positions of relations by elements of some set other than [n], e.g. by variables of a CSP. (3) If m(x, y, z) = x − y + z is the affine operation of, say, Z p , p prime, then relations invariant with respect to m are exactly those that can be represented as solution sets of systems of linear equations over Z p , and the corresponding CSP can be solved by Gaussian Elimination. One direction is easy to see.
M is the matrix of the system of equations, and a, b, c ∈ R, then The next step in discovering more structure behind nonuniform CSPs was made in [28], where universal algebras were brought into the picture. A (universal) algebra is a pair A = (A, F ) consisting of a set A, the universe of A, and a set F of operations on A. Operations from F (called basic) together with operations that can be obtained from them by means of composition are called the term operations of A.
Algebras allow for a more general definition of CSPs than the one used above. Let CSP(A) denote the class of nonuniform CSPs {CSP(Γ) | Γ ⊆ Inv(F ), Γ finite}, where Inv(F ) denotes the set of all relations invariant with respect to all operations from F . Note that the tractability of CSP(A) can be understood in two ways: as the existence of a polynomial-time algorithm for every CSP(Γ) from this class, or as the existence of a uniform polynomial-time algorithm for all such problems. One of the implications of our results is that these two types of tractability are the same. From the formal standpoint we will use the stronger one.

Structural features of universal algebras
We use some structural elements of algebras, the main of which are subalgebras, congruences, and quotient algebras. For B ⊆ A and an operation f on A by f B we denote the restriction of f on B.
Congruences play a very significant role in our algorithm, and we discuss them in more detail. A congruence is an equivalence relation α ∈ Inv(F ). This means that for any operation f ∈ F and any (a 1 , b 1 ), . . . , (a k , b k ) ∈ α it holds (f (a 1 , . . . , a k ), f (b 1 , . . . , b k )) ∈ α. Hence one can define an algebra on A/ α , the set of α-blocks, by setting f / α (a 1 / α , . . . , a k / α ) = (f (a 1 , . . . , a k ))/ α for a 1 , . . . , a k ∈ A, where a/ α denotes the α-block containing a. The algebra A/ α is called the quotient algebra modulo α. Often the fact that a, b are related by a congruence α is denoted a α ≡ b. (1) Let A be any algebra. Then the equality relation 0 A and the full binary relation (2) Let L n be an n-dimensional vector space and L ′ its k-dimensional subspace, k ≤ n. The binary relation π given by: (a, b) ∈ π iff a, b have the same orthogonal projection on L ′ , is a congruence of L n and L n / π is L ′ .
The classes of congruence θ are 0/ θ = {0, 1}, 2/ θ = {2}. Then the quotient algebra A M / θ is also basically a semilattice, as  The (ordered) set of all congruences of A is denoted by Con(A). This set is actually a lattice, that is, the operations of meet ∧ and join ∨ can be defined so that α ∧ β is the greatest lower bound of α, β ∈ Con(A) and α ∨ β is the least upper bound of α, β. Fig. 2(a) shows Con(A M ) for the algebra A M from Example 2(3). By HS(A) we denote the set of all quotient algebras of all subalgebras of A.

The Dichotomy Conjecture
The results of [28] reduce the dichotomy conjecture to idempotent algebras. An algebra A = (A, F ) is said to be idempotent if every operation f ∈ F satisfies the equation f (x, . . . , x) = x. If A is idempotent, then all the constant relations {(a)} are invariant under F . Therefore studying CSPs over idempotent algebras is the same as studying the CSPs that allow all constant relations. Another useful property of idempotent algebras is that every block of every its congruence is a subalgebra. We now can state the algebraic version of the dichotomy theorem. (2) A has a weak near-unanimity term operation; (3) every algebra from HS(A) has a nontrivial term operation (that is, not a projection, an operation of the form f (x 1 , . . . , The hardness part of this theorem is proved in [28]; the equivalence of (2) and (3) was proved in [13] and [56]. The equivalence of (1) to (2) and (3) is the main result of this paper. In the rest of the paper we assume all algebras to satisfy conditions (2), (3).
In fact, we will prove a slightly more general result. Let A be a finite class of finite idempotent similar algebras, that is, whose basic operations have the same 'names' and the corresponding arities. One may assume that such a class is produced from a single algebra A by taking subalgebras, quotient algebras and also retractions introduced in Section 5.5. Then CSP(A) denotes the class of CSP instances whose variables can have different domains belonging to A, see, e.g. [15]. We will design an algorithm for CSP(A) whenever there is a near-unanimity term for all algebras in A simultaneously.

Bounded width and the few subpowers algorithm
Leaving aside occasional combinations thereof, there are only two standard types of algorithms solving the CSP. In this section we give a brief introduction into them.

CSPs of bounded width
Algorithms of the first kind are based on the idea of local propagation, that is formally described below.
Let P = (V, C) be a CSP instance. For W ⊆ V by P W we denote the restriction of P onto W , that is, the instance (W, C W ), where for each C = s, R ∈ C, the set C W includes the constraint C W = s ∩ W, pr s∩W R , where s ∩ W is the subtuple of s containing all the elements from W in s, say, s ∩ W = (i 1 , . . . , i k ), and pr s∩W R stands for pr {i1,...,i k } R. The set of solutions of P W will be denoted by S W .
Unary solutions, that is, when |W | = 1 play a special role. As is easily seen, for v ∈ V the set S v is just the intersections of unary projections pr v R of constraints whose scope contains v. Instance P is said to be 1-minimal if for every v ∈ V and every constraint C = s, R ∈ C such that v ∈ s, it holds pr v R = S v . For a 1-minimal instance one may always assume that allowed values for a variable v ∈ V is the set S v . We call this set the domain of v and assume that CSP instances may have different domains, which nevertheless are always subalgebras or quotient algebras of the original algebra A. It will be convenient to denote the domain of v by A v . The domain A v may change as a result of transformations of the instance.
Instance P is said to be (2,3)-consistent if it has a (2,3)-strategy, that is, a collection of relations R X , X ⊆ V , |X| = 2 satisfying the following conditions (we use Let the collection of relations R X be denoted by R. A tuple a whose entries are indexed with elements of W ⊆ V and such that pr X a ∈ R X for any X ⊆ W , |X| = 2, will be called R-compatible. If a (2,3)-consistent instance P with a (2,3)-strategy R satisfies the additional condition -for every constraint C = s, R of P every tuple a ∈ R is R-compatible, it is called (2,3)-minimal. For k ∈ N, (k, k + 1)-strategies, (k, k + 1)-consistency, and (k, k + 1)-minimality are defined in a similar way replacing 2,3 with k, k + 1.
Instance P is said to be minimal (or globally minimal) if for every C = s, R ∈ C and every a ∈ R there is a solution ϕ ∈ S such that ϕ(s) = a. Similarly, P is said to be globally 1-minimal if for every v ∈ V and a ∈ A v there is a solution ϕ with ϕ(v) = a.
Any instance can be transformed to a 1-minimal, (2,3)-consistent, or (2,3)-minimal instance in polynomial time using the standard constraint propagation algorithms (see, e.g. [34]). These algorithms work by changing the constraint relations and the domains of the variables eliminating some tuples and elements from them. We call such a process tightening the instance. It is important to notice that if the original instance belongs to CSP(A) for some algebra A, that is, all its constraint relations are invariant under the basic operations of A, the constraint relations obtained by propagation algorithms are also invariant under the basic operations of A, and so the resulting instance also belongs to CSP(A). Establishing minimality amounts to solving the problem and therefore not always can be easily done.
If a constraint propagation algorithm solves a CSP, the problem is said to be of bounded width. More precisely, CSP(Γ) (or CSP(A)) is said to have bounded width if for some k every (k, k+1)-minimal instance from CSP(Γ) (or CSP(A)) has a solution. Problems of bounded width are very well studied, see an older survey [29] and a more recent paper [4]. (2) every (2,3)-minimal instance from CSP(A) has a solution; (3) A has a weak near-unanimity term of arity k for every k ≥ 3; (4) every algebra HS(A) has a nontrivial operation, and none of them is equivalent to a module (in a certain precise sense).

Omitting semilattice edges and the few subpowers property
The second type of CSP algorithms can be viewed as a generalization of Gaussian elimination, although, it utilizes just one property also used by Gaussian elimination: the set of solutions of a system of linear equations or a CSP has a set of generators of size polynomial in the number of variables. The property that for every instance P of CSP(A) its solution space S has a set of generators of polynomial size is nontrivial, because there are only exponentially many such sets, while, as is easily seen CSPs may have up to double exponentially many different sets of solutions. Formally, an algebra A = (A, F ) has few subpowers if for every n there are only exponentially many n-ary relations in Inv(F ).
Algebras with few subpowers are well studied and the CSP over such an algebra has a polynomial-time solution algorithm, see, [10,43]. In particular, such algebras admit a characterization in terms of the existence of a term operation with special properties, an edge term. We need only a subclass of algebras with few subpowers that appeared in [21,25] and is defined as follows.
A pair of elements a, b ∈ A is said to be a semilattice edge if there is a binary term  Semilattice edges have other useful properties including the following one that we use for reducing a CSP to smaller problems.
Lemma 7 (Proposition 24, [23]) For any idempotent algebra A there is a binary term operation xy of A (think multiplication) such that xy is a semilattice operation on any semilattice edge and for any a, b ∈ A either ab = a or {a, ab} is a semilattice edge.
Note that any semilattice operation satisfies the conditions of Lemma 7. The operation r of the algebra A M from Example 2(3) is not a semilattice operation (for instance, it does not satisfy the equation r(x, y) = r(y, x)), but it satisfies the conditions of Lemma 7.

Centralizers and decomposition of CSPs
In this section we introduce an alternative definition of the centralizer operator on congruence lattices studied in commutator theory, and study its properties and its connection to decompositions of CSPs. Unlike the vast majority of the literature on the algebraic approach to the CSP we use not only term operations, but also polynomial operations of an algebra. It should be noted however that the first to use polynomials for CSP algorithms was Maroti in [55]. We make use of some ideas from that paper in the next section.
Let f (x 1 , . . . , x k , y 1 , . . . , y ℓ ) be a k + ℓ-ary term operation of an algebra is called a polynomial of A. The name 'polynomial' refers to usual polynomials. Indeed, if A is a ring, its polynomials as just defined are the same as polynomials in the regular sense. A polynomial that depends on only one variable, i.e. k = 1, is said to be a unary polynomial.
While polynomials of A do not have to be polymorphisms of relations from Inv(F ), congruences and unary polynomials are in a special relationship. More precisely, it is a well known fact that an equivalence relation over A is a congruence if and only if it is preserved by all the unary polynomials of A. If α is a congruence, and f is a unary polynomial, by f (α) we denote the set of pairs Example 3 The unary polynomials of the algebra A M from Example 2(3) include the following unary operations (these are the polynomials we will use, there are more unary polynomials of A M ): The lattice Con(A M ) has 3 congruences: 0, θ, 1 (see Example 2 (3)). As is easily For an algebra A, a term operation f (x, y 1 , . . . , y k ), and a ∈ A k , let f a (x) = f (x, a). Let α, β ∈ Con(A), α ≤ β, and let (α : β) ⊆ A 2 denote the greatest congruence such that for any term operation f (x, y 1 , . . . , y k ) and any a, b ∈ A k such that Polynomials of the form f a , f b are often called twin polynomials.
The congruence (α : β) will be called the centralizer of α, β 2 . The following statement is one of the key ingredients of the algorithm.

For the first centralizer it suffices to demonstrate that the condition in the definition of centralizer is satisfied for pairs of twin polynomials of the form
Interestingly, Lemma 8 implies that if we change the operation r in just one point, it has a profound effect on the centralizer (0 : θ). Let A N be the same algebra as A M with operations r ′ , t ′ defined in the same way as r, t, except r ′ (2, 1) = 1 replacing the value r(2, 1) = 0. In this case {1, 2} is also a semilattice edge, see Fig. 1 shows the effect of large centralizers (α : β) on the structure of algebra A, which is a generalization of the phenomena observed in Example 4. Dots there represent α-blocks (assume α is the equality relation), ovals represent β-blocks, let they be B and C, and such that there is at least one semilattice edge between B and C. If (α : β) is the full relation, Lemmas 7 and 8 imply that for any a ∈ B and any b, c ∈ C we have ab = ac, and so ab is the only element of C such that {a, ab} is a semilattice edge (represented by arrows). In other words, we have a mapping from B to C that can also be shown injective. We will use this mapping to lift any solution with a value from B to a solution with a value from C. Finally, we prove an easy corollary from Lemma 8.

The algorithm
In this section we introduce the reductions used in the algorithm, and then explain the algorithm itself. The reductions heavily use the algebraic structure of the domains of an instance, and the structure of the instance itself.

Decomposition of CSPs
We have seen in the previous section that large centralizers impose strong restrictions on the structure of an algebra. We start this section showing that small centralizers imply certain properties of CSP instances, as well.
Let R be a binary relation, a subdirect product of A × B, and α ∈ Con(A), γ ∈ Con(B). Relation R is said to be αγ-aligned if, for any (a, c), This means that if A 1 , . . . , A k are the α-blocks of A, then there are also k γ-blocks of B and they can be labeled B 1 , . . . , B k in such a way that This definition provides a way to decompose CSP instances. Let P = (V, C) be a (2,3)-minimal instance from CSP(A). We will always assume that a (2,3)-consistent or (2,3)-minimal instance has a constraint C X = X, R X = S X for every X ⊆ V , |X| ≤ 2. So, C contains a constraint C vw = (v, w), R vw for every v, w ∈ V , and these relations form a (2,3)-strategy for P. Recall that A v denotes the domain of v ∈ V . Let W ⊆ V and α v ∈ Con(A v ), v ∈ W , be such that for any v, w ∈ W the relation R vw is α v α w -aligned. The set W is then called a strand of P. We will also say that P W is α-aligned.
For a strand W and congruences α v as above there is a one-to-one correspondence between α v -and α w -blocks of A v and A w , v, w ∈ W . Moreover, by (2,3)-minimality these correspondences are consistent, that is, if u, v, w ∈ W and B u , B v , B w are α u -, This means that P W can be split into several instances, whose domains are α v -blocks.
Lemma 10 Let P, W, α v for each v ∈ W , be as above. Then P W can be decomposed into a collection of instances P 1 , . . . , P k , k constant, P i = (W, C i ) such that every solution of P W is a solution of one of the P i and for every v ∈ W its domain in P i is an α v -block.

Example 5 Let A M be the algebra introduced in Example 2(3), and R is the following ternary relation over
To make the instance (2,3)-minimal we run the appropriate local propagation algorithm on it. First, such an algorithm adds new binary constraints It then iteratively removes pairs from these relations that do not satisfy the (2,3)-minimality condition. Similarly, it tightens the original constraint relations if they violate the conditions of (2,3)-minimality. It is not hard to see that this algorithm does not change constraints C 1 , C 2 , and that the new binary relations are as follows:

Irreducibility
In order to formulate the algorithm properly we need one more transformation of algebras. An algebra A is said to be subdirectly irreducible if the intersection of all its nontrivial (different from the equality relation) congruences is nontrivial. This smallest nontrivial congruence µ A is called the monolith of A, see Fig. 2(b). For instance, the algebra A M from Example 2(3) is subdirectly irreducible, because it has the smallest nontrivial congruence, θ. It is a folklore observation that any CSP instance can be transformed in polynomial time to an instance, in which the domain of every variable is a subdirectly irreducible algebra. We will assume this property of all the instances we consider.

Block-minimality
Using Lemma 10 we introduce a new type of consistency of a CSP instance, blockminimality, which will be crucial for our algorithm. In a certain sense it is similar to the standard local consistency notions, as it also defined through a family of relations that have to be consistent in a certain way. However, block-minimality is not quite local, and is more difficult to establish, as it involves solving smaller CSP instances recursively. The definitions below are designed to allow for an efficient procedure to establish block-minimality. This is achieved either by allowing for decomposing a subinstance into instances over smaller domains as in Lemma 10, or by replacing large domains with their quotient algebras.
Example 6 Consider the instance P from Example 5, and let α vi = θ i for each i ∈ [5].
Then P/ α is the instance over A M / θ given by Recall that an algebra A v is said to be semilattice free if it does not contain semilattice edges. Let size(P) denote the maximal size of domains of P that are not semilattice free and MAX(P) be the set of variables The definition of block-minimality is designed in such a way that block-minimality can be efficiently established. Observe that a strand can be large, even equal to V . However P /U splits into a union of disjoint problems over smaller domains.
As is easily seen, any assignment to v 1 , v 2 , v 3 or to v 2 , v 4 , v 5 can be extended to a solution of P /{v2} . ⋄ For an instance P we say that an instance P ′ is strictly smaller than instance P if size(P ′ ) < size(P).
Lemma 11 Let P = (V, C) be a (2,3)-minimal instance. Then P can be transformed to an equivalent block-minimal instance P ′ by solving a quadratic number of strictly smaller CSPs.
Proof: To establish block-minimality of P, for every strand U ⊆ V , we need to check if the problem given in condition (BM) is minimal. If they are then P is blockminimal, otherwise some tuples can be removed from some constraint relation R (the set of tuples that remain in R is always a subalgebra, as is easily seen), and the instance P tightened, in which case we need to repeat the procedure with the tightened instance. Therefore we just need to show how to reduce solving those subproblems to solving strictly smaller CSPs.
By the definition of a strand there is a partition B w1 , . . . , B wℓ of A w for w ∈ U such that for every constraint s, R ∈ C, for any w 1 , w 2 ∈ s ∩ U , any b ∈ R, and . Then the problem P /U is a disjoint union of instances P 1 , . . . , P ℓ given by: In order to establish the minimality of P /U it suffices to do the following. Take C = s, R ∈ C and a ∈ R. We need to check that a ′ = a/ µ Y , Y = MAX(P) − U , extends to a solution of at least one of the problems P 1 , . . . , P ℓ . For i ∈ [ℓ] let P ′ i be the problem obtained from P i as follows: fix the values of variables from s to those of a ′ , or in other words, add the constraint (w), {a[w]/ µ Y w } for each w ∈ s. Then a ′ can be extended to a solution of P i if and only if P ′ i has a solution. ✷

The algorithm
We are now in a position to describe our solution algorithm. In the algorithm we distinguish three cases depending on the presence of semilattice edges and centralizers of the domains of variables. In each case we employ different methods of solving or reducing the instance to a strictly smaller one. Algorithm 1, SolveCSP, gives a more formal description of the solution algorithm.
Semilattice free domains. If all domains of P are semilattice free then P can be solved in polynomial time, using the few subpowers algorithm, as shown in [43,21].
Small centralizers If µ * v = 0 v for all v ∈ V , by Theorem 12 block-minimality guarantees that a solution exists, and we can use Lemma 11 to solve the instance. Large centralizers Suppose that MAX(P) ∩ Center(P) = ∅. In this case the algorithm proceeds in three steps. Stage 1. Consider the problem P/ µ * . We establish the global 1-minimality of this problem. If it is tightened in the process, we start solving the new problem from scratch.
To check global 1-minimality, for each v ∈ V and every a ∈ A v / µ * v , we need to find a solution of the instance, or show it does not exists. To this end, add the constraint (v), {a} to P/ µ * . The resulting problem belongs to CSP(A), since A v is idempotent, and hence {a} is a subalgebra of A v / µ * v . Then we establish (2,3)-minimality and block minimality of the resulting problem. Let us denote it P ′ . There are two possibilities. First, if size(P ′ ) < size(P) then P ′ is a problem strictly smaller than P and can be solved by recursively calling Algorithm 1 on P ′ . If size(P ′ ) = size(P) then, as all the domains A v of maximal size for v ∈ Center(P) are replaced with their quotient algebras, there is w ∈ Center(P) such that |A w | = size(P) and A w is not semilattice free. Therefore for every u ∈ Center(P ′ ), for the corresponding domain A ′ u we have |A ′ u | < size(P) = size(P ′ ). Thus, MAX(P ′ )∩Center(P ′ ) = ∅, and P ′ has a solution by Theorem 12.
Such a semilattice edge exists, because A v is not semilattice free. Also, if µ * v = 0 v , then v ∈ Center(P) and (0 v : µ v ) = 1 v and by Corollary 9 its semilattice edges are all between µ v -blocks. Since P/ µ * is globally 1-minimal, there is a solution ϕ v,b such that ϕ v,b (v) = b, and therefore ϕ v,b satisfies the condition. Let MAX(P) = {v 1 , . . . , v ℓ } and b 1 , . . . , b ℓ the values satisfying the requirements above. STAGE 3. We apply the transformation of P suggested by Maroti in [55]. For a solution ϕ of P/ µ * , by P · ϕ we denote the instance (V, C ϕ ) given by the rule: for every By the results of [55] and Lemma 8 the instance P · ϕ has a solution if and only if P does. We now use the solutions ϕ v1,b1 , . . . , ϕ v ℓ ,b ℓ to construct a new problem Note that the transformation of P above boils down to a collection of mappings p v : so called consistent mappings, see Section 5.5, that also satisfy some additional properties. If we now repeat the procedure above starting from P 1 and using the same solutions ϕ vi,bi , we obtain an instance P 2 , for which the corresponding collection of consistent mappings is p v • p v , v ∈ V . More generally, There is k such that p k v is idempotent for every v ∈ V , that is, for all x. Set P † = P k . We will show later that size(P † ) < size(P).
This last case can be summarized as the following Theorem 13 If P/ µ * is globally 1-minimal, then P can be reduced in polynomial time to a strictly smaller instance over a class of algebras satisfying the conditions of the Dichotomy Conjecture.

11:
If size(P ′′ ) < size(P) call SolveCSP on P ′′ and flag a if P ′′ has no solution 12: Establish block-minimality of P ′′ ; if the problem changes, return to Step 10 13: If the resulting instance is empty, flag the element a 14: end for 15: If there are flagged values, tighten the instance by removing the flagged elements and start over 16: Use Theorem 13 to reduce P to an instance P † with size(P † ) < size(P) 17: Call SolveCSP on P † and RETURN the answer It is an easy exercise to show that this instance is globally 1-minimal (every value 0/ θ can be extended to the all-0/ θ solution, and every value 2/ θ can be extended to the all-2/ θ solution). This completes Stage 1. For every variable v i we choose b ∈ A M / θ such that for some a ∈ A M / θ the pair {a, b} is a semilattice edge. Since A M / θ is a 2-element semilattice, setting b = 0/ θ and a = 2/ θ is the only choice. Therefore ϕ vi,bi in our case can be chosen to be the same solution ϕ given by ϕ(v i ) = 0/ θ ; and Stage 2 is completed. For Stage 3 first note that in A M the operation r plays the role of multiplication ·. Then for each of the constraints C 1 , C 2 choose a representative and are invariant with respect to the affine operation of Z 2 . Therefore the instance P ′ can be viewed as a system of linear equations over Z 2 (this system is actually empty in our case), and can be easily solved. ⋄ Using Lemma 11 and Theorems 12,13 it is not difficult to see that the algorithm runs in polynomial time. Proof: By the results of [21,25] the algorithm correctly solves the given instance P in polynomial time if the conditions of Step 1 are true. Lemma 11 implies that Steps 4 and 12 can be completed by recursing to strictly smaller instances.
Next we show that the for-loop in Steps 8-14 checks if P * = P/ µ * is globally 1-minimal. For this we need to verify that a value a is flagged if and only if P * has no solution ϕ with ϕ(v) = a, and therefore if no values are flagged then P * is globally 1minimal. If ϕ(v) = a for some solution ϕ of P * , then ϕ is a solution P ′ constructed in Step 9. In this case Steps 11,12 cannot result in an empty instance. Suppose a ∈ A v / µ * v is not flagged. If size(P ′′ ) < size(P) this means that P ′′ and therefore P ′ has a solution. Otherwise this means that establishing block-minimality of P ′′ is successful.
This in turn implies that P ′ has a solution. Observe also that the set of unflagged values for each variable v ∈ V is a subalgebra of A/ µ * . Indeed, the set of solutions of P * is a subalgebra S * of v∈V A/ µ * , and the set of unflagged values is the projection of S * on the coordinate position v.
Finally, if Steps 8-15 are completed without restarts, Steps 16,17 can be completed by Theorem 13, and recursing on P ′ such that either size(P ′ ) < size(P) or MAX(P ′ )∩

Center(P ′ ) = ∅.
To see that the algorithm runs in polynomial time it suffices to observe that (1) The number of restarts in Steps 4 and 15 is at most linear, as the instance becomes smaller after every restart; therefore the number of times Steps 4-15 are executed together is at most linear.
(2) The number of iterations of the for-loop in Steps 8-14 is linear.
(3) The number of restarts in Steps 10 and 12 is at most linear, as the instance becomes smaller after every iteration. (4) Every call of SolveCSP when establishing block-minimality in Steps 4, and 12 is made on an instance strictly smaller than P, and therefore the depth of recursion is bounded by size(P) in Step 4,11,12 and 17.
Thus a more thorough estimation gives a bound on the running time of O(n 3k ), where k is the maximal size of an algebra in A. ✷

Proof of Theorem 13
Following [55] let P = (V, C) be an instance and p v : are said to be consistent if for any s, R ∈ C, s = (v 1 , . . . , v k ), and any tuple a ∈ R the tuple (p v1 (a[1]), . . . , p v k (a[k])) belongs to R. It is easy to see that the composition of two families of consistent mappings is also a consistent mapping. For consistent idempotent mappings p v by p(P) we denote the retraction of P, that is, P restricted to the images of p v . In this case P has a solution if and only if p(P) has, see [55]. Let ϕ be a solution of P/ µ * . We define p ϕ v : , and k is such that q k v is idempotent for all v ∈ V . Note that by Lemma 8 this mapping is properly defined even if µ * v = 0 v .
Proof: Take any C = s, R ∈ C. Since ϕ is a solution of P/ µ * , there is b ∈ R such that b[v] ∈ ϕ(v) for v ∈ s. Then for any a ∈ R, q(a) = a · b ∈ R, and this product does not depend on the choice of b, as it follows from Lemma 8. Iterating this operation also produces a tuple from R.
has a weak near-unanimity term operation. We use the inductive definition of P † given in Stage 3.
where if µ * v = µ v by Lemma 8 the multiplication by ϕ vj ,bj (v) does not depend on the choice of a representative from ϕ vj ,bj (v). By Lemma 15 {p vi } for every i, and so {p v } and {p k v } are collections of consistent mappings. Now (a) follows from [55]. Next we show that for every j ≤ i ≤ ℓ it holds that |p vi (A vj )| < |A vj |. Since applying mappings to a set does not increase its cardinality, this implies (b). If |p vj−1 (A vj )| < |A vj |, we have the desired inequality applying the observation in the previous sentence. Otherwise a j ∈ A vj = p vj−1 (A vj ), and it suffices to notice that a j · ϕ vj ,bj ( To prove (c) observe that if A v is semilattice free then p ϕ v is the identity mapping for any ϕ by Lemma 7, and so A † v = A v . For the remaining domains let f be a weak near-unanimity term of the class A. Then for any idempotent mapping p the operation p • f given by (p • f )(x 1 , . . . , x n ) = p(f (x 1 , . . . , x n )) is a weak near-unanimity term of p(A) = {p(A) | A ∈ A}. The result follows. ✷

Algebra technicalities
The rest of the paper is dedicated to proving Theorem 12. This part assumes some familiarity with algebraic terminology. A brief review of the necessary facts from universal algebra can be found in [26]. In this section we remind some results from [26] necessary for our proof.

Coloured graphs
In [16,30] we introduced a local approach to the structure of finite algebras. As we use this approach in the proof of Theorem 12, we present the necessary elements of it here, see also [23,24]. For the sake of the definitions below we slightly abuse terminology and by a module mean the full idempotent reduct of a module.
For an algebra A the graph G(A) is defined as follows. The vertex set is the universe A of A. A pair ab of vertices is an edge if and only if there exists a maximal congruence θ of Sg(a, b), and a term operation f of A such that either Sg(a, b)/ θ is a module and f is an affine operation on it, or f is a semilattice operation on {a/ θ , b/ θ }, or f is a majority operation on {a/ θ , b/ θ }. (Note that we use the same operation symbol in this case.) If there are a maximal congruence θ and a term operation f of A such that f is a semilattice operation on {a/ θ , b/ θ } then ab is said to have the semilattice type. An edge ab is of majority type if there are a maximal congruence θ and a term operation f such that f is a majority operation on {a/ θ , b/ θ } and there is no semilattice term operation on {a/ θ , b/ θ }. Finally, ab has the affine type if there are θ and f such that f is an affine operation on Sg(a, b)/ θ and Sg(a, b)/ θ is a module. Pairs of the form {a/ θ , b/ θ } will be referred to as thick edges.
Properties of G(A) are related to the properties of the algebra A.

Theorem 16 (Theorem 5 of [23]) Let A be an idempotent algebra A such that var(A) omits type 1. Then
(1) any two elements of A are connected by a sequence of edges of the semilattice, majority, and affine types; (

2) var(A) omits types 1 and 2 if and only if G(A) satisfies the conditions of item (1) and contains no edges of the affine type.
We use the following refinement of this construction. Let A be a finite class of finite smooth algebras. A ternary term operation g ′ of A is said to satisfy the majority condition for A if g ′ is a majority operation on every thick majority edge of every algebra from A. A ternary term operation h ′ is said to satisfy the minority condition for A if h ′ is a Mal'tsev operation on every thick affine edge. Operations satisfying the majority and minority conditions always exists, as is proved in [23,Theorem 21]. Fix an operation h satisfying the minority condition, it can also be chosen to satisfy the equation h(h(x, y, y), y, y) = h(x, y, y). A pair of elements a, b ∈ A ∈ A is said to be (1) a semilattice edge if there is a term operation f such that f (a, b) = f (b, a) = b; (2) a thin majority edge if for any term operation g ′ satisfying the majority condition the subalgebras Sg(a, g ′ (a, b, b)), Sg(a, g ′ (b, a, b)), Sg(a, g ′ (b, b, a)) contain b.
(3) a thin affine edge if h(b, a, a) = b and b ∈ Sg(a, h ′ (a, a, b)) for any term operation h ′ satisfying the minority condition.
Note that thin edges are directed, as a and b appear asymmetrically. By G ′ (A) we denote the graph whose vertices are the elements of A, and the edges are the thin edges defined above. Theorem 21 from [23] also implies that there exists a binary term operation · of A that is a semilattice operation on every thin semilattice edge. We distinguish several types of paths in G ′ (A) depending on the types of edges involved. A directed path in G ′ (A) is called an asm-path, if there is an asm-path from a to b we write a ⊑ asm b. If all edges of this path are semilattice or affine, it is called an affine-semilattice path or an as-path, if there is an as-path from a to b we write a ⊑ as b.
We consider strongly connected components of G ′ (A) with majority edges removed, and the natural partial order on such components. The maximal components will be called as-components, and the elements from as-components are called as-maximal; the set of all as-maximal elements of A is denoted by amax(A). An alternative way to define as-maximal elements is as follows: a is as-maximal if for every b ∈ A such that a ⊑ as b it also holds that b ⊑ as a. Finally, element a ∈ A is said to be universally maximal (or u-maximal for short) if for every b ∈ A such that a ⊑ asm b it also holds that b ⊑ asm a. The set of all u-maximal elements of A is denoted umax(A).
U-maximality has additional useful properties.

(2) Let B be a subalgebra of A containing a u-maximal element of A. Then every element u-maximal in B is also u-maximal in A. In particular, if α is a congruence of A and B is a u-maximal α-block, that is B is a u-maximal element in
Relations, or, more generally subdirect products of algebras can be naturally endowed with a graph structure: Let R be a subdirect product of A 1 × · · · × A n . A pair a, b ∈ R is a thin {semilattice, majority, affine} edge if for every i ∈ [n] the pair (in the latter case it will often be convenient to call a pair of equal elements a thin edge of whatever type we need). Paths and maximality can also be lifted to subdirect products.
(1) For any a ∈ R, and an as-path (asm-path) b 1 , . . . , b k ∈ pr I R with pr I a = b 1 , there is an as-path (asm- (3) If a ∈ R is a as-maximal or u-maximal element then so is pr I a.
We complete this section with an auxiliary statement that will be needed later.

Quasi-decomposition and rectangularity
We make use of the property of quasi-2-decomposability proved in [24].
Theorem 20 (The 2-Decomposition Theorem 30, [24]) If R is an n-ary relation, X ⊆ [n], tuple a is such that pr J a ∈ pr J R for any J ⊆ [n], |J| = 2, and pr X a ∈ amax(pr X R), there is a tuple b ∈ R with pr J a ⊑ as pr J b for any J ⊆ [n], |J| = 2, and pr X b = pr X a.
Another property of relations was also introduced in [24] and is similar to the rectangularity property of relations with a Mal'tsev polymorphism. Let R be a subdirect product of A 1 , A 2 . By lk 1 , lk 2 we denote the congruences of A 1 , A 2 , respectively, generated by the sets of pairs {(a, b) 1 such that (c, a), (c, b) ∈ R}, respectively. Congruences lk 1 , lk 2 are called link congruences. Relation R is said to be linked if the link congruences are full congruences.
Proposition 21 (Corollary 28, [24]) Let R be a subdirect product of A 1 and A 2 , lk 1 , lk 2 the link congruences, and let B 1 , B 2 be as-components of a lk 1 -block and a lk 2 -block, In particular, if R is linked and B 1 , B 2 are as-components of A 1 , A 2 , respectively,

Separating congruences
Let A be a finite algebra and α, β ∈ Con(A). The pair α, β is said to be a prime interval, denoted α ≺ β if α < β and for any γ ∈ Con(A) with α ≤ γ ≤ β either α = γ or β = γ. For α ≺ β, an (α, β)-minimal set is a set minimal with respect to inclusion among the sets of the form f (A), where f is a unary polynomial of A such that f (β) ⊆ α.
In a similar way separation can be defined for prime intervals in different coordinate positions of a relation. Let R be a subdirect product of A 1 × · · · × A n . Then R is also an algebra and its polynomials can be defined in the same way as for a single algebra. Let i, j ∈ [n] and let α ≺ β, γ ≺ δ be prime intervals in Con(A i ) and Con(A j ), respectively. Interval (α, β) can be separated from (γ, δ) if there is a unary polynomial f of R such that f (β) ⊆ α but f (δ) ⊆ γ (note that the actions of f on A i , A j are polynomials of those algebras).
If A 1 , . . . , A n are algebras and B 1 , . . . , B n are their subsets B i ⊆ A i , i ∈ [n], and α 1 , . . . , α n are congruences of the A i 's, it will be convenient to denote B 1 × · · · × B n by B and By Cg A (D), or just Cg(D) if A is clear from the context, we denote the congruence of A generated by a set D of pairs from A 2 .
For an algebra A, a set U of unary polynomials, and B ⊆ A 2 , we denote by  (a, b) ∈ B, f ∈ U}. Let also α, β ∈ Con(A), α ≤ β and D a subuniverse of A such that β = Cg A (α ∪ {(a, b)}) for some a, b ∈ D. We say that α and β are U- Let β i ∈ Con(A i ), let B i be a β i -block for i ∈ [n], and let R ′ = R∩B, B ′ i = pr i R ′ . A unary polynomial f is said to be B-preserving if f (B) ⊆ B. We call an n-ary relation R chained with respect to β, B if (Q1) for any I ⊆ [n] and α, β ∈ Con(pr I R) such that α ≤ β ≤ β I , α, β are U Bchained with respect to pr I R ′ , and U B is the set of all B-preserving polynomials of R; (Q2) for any α, β ∈ Con(pr I R), γ, δ ∈ Con(A j ), j ∈ [n], such that α ≺ β ≤ β I , γ ≺ δ ≤ β j , and (α, β) can be separated from (γ, δ), the congruences α and β are U(γ, δ, B)-chained with respect to pr I R ′ , where U(γ, δ, B) is the set of all Bpreserving polynomials g of R such that g(δ) ⊆ γ.
The following lemma claims that the property to be chained is preserved under certain transformations of β and B.
Let again R be a subdirect product of A 1 × · · · × A n and let W R denote the set of triples (i, α, β), where i ∈ [n] and α, β ∈ Con(A i ), α ≺ β. We say that (i, α, β) cannot be separated from (j, γ, δ) if (α, β) cannot be separated from (γ, δ) in R. Then the relation 'cannot be separated' on W R is clearly reflexive and transitive. The next lemma shows that it is to some extent symmetric.
We also introduce polynomials that collapse all prime intervals in congruence lattices of factors of a subproduct, except for a set of intervals that cannot be separated from each other.

The Congruence Lemma
This section contains a technical result, the Congruence Lemma 26, that will be used when proving Theorem 12. We start with introducing two closure properties of algebras and their subdirect products. Although we do not need as-closeness right now, it fits well with polynomial closeness. Let R be a subdirect product of A 1 , . . . , A n and Q a subalgebra of R. We say that Q is polynomially closed in R if for any polynomial f of R the following condition holds: for any a, b ∈ umax(Q) such that f (a) = a and for any c ∈ Sg(a, f (b)) such that a ⊑ as c in Sg(a, f (b)), the tuple c belongs to Q. A subset S ⊆ Q is as-closed in Q if for any a, b ∈ Q with a ∈ umax(S), a ⊑ as b in Q, it holds b ∈ S. The set S is said to be weakly as-closed in Q if for any i ∈ [n], pr i S is as-closed in pr i Q.
Polynomially closed subalgebras and as-closed subsets are well behaved with respect to some standard algebraic transformations.
Lemma 25 (Lemma 42, [26]) (1) For any R, R is polynomially closed in R and R is as-closed in R.

∅. Then Q is polynomially closed in R.
If also S i ⊆ Q i are as-closed in Q i , then S = Φ(S 1 , . . . , S k ) is as-closed in Q.
(3) Let R be a subdirect product of A 1 , . . . , A n , β i ∈ Con(A i ), i ∈ [n], and let Q be polynomially closed in R. Then Q/ β is polynomially closed in R.
If S ⊆ Q is as-closed in Q then S/ β is as-closed in Q/ β .
We are now in a position to state the Congruence Lemma. Let R be a subdirect product of A 1 × A 2 , β 1 , β 2 congruences of A 1 , A 2 , and let B 1 , B 2 be β 1 -and β 2blocks, respectively. Also, let R be chained with respect to (β 1 , β 2 ), (B 1 , B 2 ) and Lemma 26 (The Congruence Lemma, Lemma 43, [26]) Suppose α = 0 1 and let R ′ be a subalgebra of R * polynomially closed in R and such that B ′ 1 = pr 1 R ′ contains an as-component C of B * 1 and R ′ ∩ umax(R * ) = ∅. Let β ′ be the least congruence is the graph of a mapping ϕ : B ′′ 2 → C such that the kernel of ϕ is the restriction of η on B ′′ 2 .

Decompositions and compressed problems
In this section we apply the machinery developed in the previous section to constraints satisfaction problems in order to prove Theorem 12.

Decomposition of CSPs
We begin with showing how separating congruence intervals and centralizers can be combined to obtain strands and therefore useful decompositions of CSPs. The case of binary relations is settled in [26].

Theorem 28 Let P = (V, C) be a (2,3)-minimal instance and
Theorem 28 relates domains with congruence intervals that cannot be separated with strands.
Corollary 29 Let P = (V, C) be a (2,3)-minimal instance and W a non-central coherent set. Then W is a subset of a strand.
For technical reasons we will also count the empty set as a non-central coherent set.

Compressed problems
In this section we define a way to tighten a block-minimal problem instance in such a way that it remains (similar to) block-minimal. More precisely, we introduce several properties of a subproblem of a CSP instance P that are preserved when the problem is restricted in a certain way.
Let P = (V, C) be a (2,3)-minimal and block-minimal instance over A. Recall that for a strand W ⊆ V by P /W we denote the problem P/ µ /W , where µ /W = µ Y and Y = MAX(P) − W . Let also S /W denote the set of solutions of P /W . If W is a non-central coherent set, the problem P /W is defined in the same way.
Lemma 30 Let P be a (2,3)-minimal and block minimal problem. Then for every noncentral coherent set W the problem P /W is minimal.
Proof: By Corollary 29 there is a strand U ⊆ V such that W ⊆ U . It now suffices to observe that for every solution ϕ ∈ S /U of P /U the mapping ϕ/ µ /W is a solution of and only if s, R ∈ C, is said to be (β, B)-compressed from P if the following conditions hold: (S1) For every s, R ∈ C the relation R † is a nonempty subalgebra of R ∩ B; (S2) the relations R X † , where R X † is obtained from R X for X ⊆ V , |X| ≤ 2, form a nonempty (2, 3)-strategy for P † ; (S3) for every non-central coherent set W the problem P † /W = P † / µ /W is minimal; (S4) for every s, R ∈ C the relation R is chained with respect to β, B, and the relation S /W is chained with respect to β, B for every non-central coherent set W ⊆ V ; (S5) for every s, R ∈ C the subalgebra R † is polynomially closed in R; (S6) for every s, R ∈ C the subalgebra R † is weakly as-closed in R ∩ B.
Conditions (S1)-(S3) are the conditions we actually want to maintain when constructing a compressed instance, and these are the ones that provide the desired results. However, to prove that (S1)-(S3) are preserved under transformations of compressed instances we also need more technical conditions (S4)-(S6).
We now show how we plan to use compressed instances. Let P be a subdirectly irreducible, (2,3)-minimal, and block-minimal instance, Then as is easily seen the instance P itself is (β, B)-compressed from P. Also, by (S1) a (γ, D)-compressed instance with γ v = 0 v for all v ∈ V gives a solution of P. Our goal is therefore to show that a (β, B)-compressed instance for any β and an appropriate B can be 'reduced', that is, transformed to a (β ′ , B ′ )-compressed instance for some β ′ < β. Note that this reduction of instances is where the condition Section 5.4). Then by conditions (S1)-(S6) we only have information about solutions to problems of the form P/ µ * or something very close to that. Therefore this barrier cannot be penetrated. We consider two cases.
This case is considered in Section 8.
This case is considered in Section 9.
There is also the possibility that In this case we can replace β v with a smaller congruence without violating any of the conditions (S1)-(S6).

Proof of Theorem 12: Affine factors
In this section we consider Case 1 of tightening instances: there is α ∈ Con(A v ) for some v ∈ V such that α ≺ β v and typ(α, β v ) = 2.

Tightening the instance and induced congruences
Let P = (V, C) be a block-minimal instance with subdirectly irreducible domains, is a module, and therefore B is as-maximal in this set. In this section we show how P † can be transformed to a (β , and let S † /U denote the set of solutions of P † /U for a non-central coherent set U . We use P † /∅ , S † /∅ to denote such a problem and its solution set for The following two statements show how relations R ‡ are related to R † . They amount to saying that either R ‡ is (almost) the intersection of R † with a block of a congruence of R, or umax(R ‡ ) = umax(R † ). Recall that for congruences β w , w ∈ V , and U ⊆ V by β U we denote the collection (β w ) w∈U .
Lemma 31 Let C = s, R ∈ C, and let S • , S • † be the set of solutions of P /W (respectively, There is a congruence τ C of R satisfying the following conditions. If, according to item (b) of the lemma, τ C R † = β s R † , we say that τ C is the full congruence; if the latter option of item (b) holds we say that τ C is a maximal congruence.
Proof: If v ∈ s then set τ C to be β s ∧ α, where α is viewed as a congruence of R † , equal to α × x∈s−{v} 1 x . Otherwise consider Q = pr s∪{v} S • as a subdirect product of A v and pr s S • . This relation is chained with respect to β, B by (S4) for P † and pr s∩{v} S • † is polynomially closed in Q by (S5) for P † and Lemma 25(2); apply the Congruence Lemma 26 to it. Specifically, consider Q/ α as a subdirect product of pr s S • and A v / α . If the first option of the Congruence Lemma 26 holds, set τ C = β s . If the second option is the case, choose τ C to be the congruence η of pr s S • identified in the Congruence Lemma 26. Note that in the latter case the restriction of τ C on R † is nontrivial, because tuples from a τ C -block are related in Q only to elements from one α-block, while the domain of v in Q spans more than one α-block.
(a) In this case the result follows by the Congruence Lemma 26.
To show that τ C ≺ β s , as β w , w ∈ s, is the smallest congruence for which R w † is a subset of a β w -block, it suffices to prove that for any a, b ∈ R † and such that a τC ≡ b, R † is in a γ-block, where γ = Cg R (τ C ∪ {a, b}). Consider again the relation Q and let Tuples a, b can be chosen u-maximal in their τ c -blocks. Let also (a ′ , a), (b ′ , b) ∈ Q; then a α ≡ b and a can be chosen u-maximal in its α-block. Since α ≺ β v and B v / α is a module, for any α-block D ⊆ B v there is c ∈ D such that {a, c} is an (α, β w )-subtrace. By Lemma 24 there is a polynomial f of pr s∪{v} S • such that f (a ′ , a) = (a ′ , a) and f (b ′ , b) = (c ′ , c) for some c ′ ∈ R ′ . Indeed, we start with any polynomial g that maps a/ α , b/ α to a/ α , c/ α and g(A v ) is an (α, β v )minimal set. Then by Lemma 24 it can be amended in such a way that g(a) = a and g(a ′ ) = a ′ . Since a/ α b/ α is an affine edge there is also (d, d) ∈ Sg Q ((a ′ , a), (c ′ , c)) such that (a ′ , a)(d ′ , d) is a thin affine edge and d α ≡ c. Since Q is polynomially closed (d, d) ∈ Q. On the other hand, as (d, d) ∈ Sg Q ((a ′ , a), (c ′ , c)), there is a term operation h such that (d, d) = h((a ′ , a), (c ′ , c). The polynomial h(f (a ′ , a), f (x)) maps (a ′ , a) to (a ′ , a) and (b ′ , b) to (d, d), proving that any two τ C blocks of R † are γrelated. ✷ Next we identify variables w ∈ V for which β ′ w has to be different from β w . Since P is (2,3)-minimal, for every w ∈ V there is C w = (w), R w ∈ C. For w ∈ W there are two cases. In the first case, when τ C w is the full congruence, we set β Lemma 32 In the notation above If γ, δ are considered as congruences of R, this condition means that (τ C , β s ) and (γ, δ) cannot be separated.
(2) Assuming MAX(P) ∩ Center(P) = ∅, if (v, α, β v ) ∈ W ′ , then for any w ∈ MAX(P), the interval (0 w , µ w ) can be separated from (α, β v ) or the other way round, and therefore either (0 w , µ w ) can be separated from every (τ C , β s ), where C ∈ C is such that τ C is a maximal congruence, or the other way round.
Proof: (1) Let S • be defined as in Lemma 31 and τ C a maximal congruence. Take a polynomial f of R. Since P is a block-minimal instance, the polynomial f can be extended from a polynomial on R to a polynomial of S • , and, in particular, to a polynomial of pr s∪{v} S • ; we keep notation f for those polynomials. Since τ C is maximal, by the Congruence Lemma 26 the intervals (α, β v ) and (τ C , β s ) in the congruence lattices of A v and R, respectively, cannot be separated in pr s∪{v} S • . Therefore f (β v ) ⊆ α if and only if f (β s ) ⊆ τ C . Since (α, β v ) and (γ, δ) cannot be separated in P, the first inclusion holds if and only if f (δ) ⊆ γ, and we infer the result.
Lemma 34 Condition (S5) for P ‡ holds. That is, for every s, R ∈ C the relation R ‡ is polynomially closed in R.
Proof: Let f be a polynomial of R, and let a, b ∈ R be tuples satisfying the conditions of polynomial closeness. Let c ∈ Sg(a, f (b)) be such that a ⊑ as c in Sg(a, f (b)). By (S5) for P † , c ∈ R † . It suffices to show that c is in the same τ C block as a. However, this is straightforward, because a τC ≡ b, and as f (a) = a, we also have a Finally, condition (S6) also holds.

Lemma 35 Condition (S6) for P ‡ holds.
Proof: Let C = s, R ∈ C. By Lemma 31(a) either umax(R ‡ ) = umax(R † ), in which case we are done, or R ‡ = R † ∩ T , where T is a τ C -block. If w ∈ s − W , then umax(pr w R ‡ ) = umax(pr w R † ) and the property of weak as-closeness holds for such variables. Otherwise if s ∩ W = ∅, R ‡ = R † ∩ B ′ . Moreover for any a ∈ R † and any w, u ∈ s ∩ W it holds a[w] ∈ B ′ w if and only if a[u] ∈ B ′ u . Let a ∈ umax(pr w R ‡ ) ⊆ umax(pr w R † ) and b ∈ pr w (R ∩ B ′ ) such that a ⊑ as b in Then, as we ob-

Condition (S2)
Property (S2) is more difficult to prove. We start with a construction similar to what we used before and that we will also use in the proof of (S3).
Let S • be the set of solutions of P • = P/ µ • . Then for C = s, R ∈ C we define Q C to be a subalgebra of the product R × A v / α that consists of all tuples (b, c ′ ), b ∈ R, such that, there is a solution ϕ ∈ S • with b ∈ ϕ(s), and ϕ(v) ∈ c ′ . By the block-minimality of P the relation Q C is indeed a subdirect product of R and A v / α , and by (S3) for P † we have Q C ∩ (R † × R v † / α ) is a subdirect product of R † and R v † / α ). Also, by Lemma 25(2,3) Q C is polynomially closed.
Let Q x = Q C xw , Q y = Q C yw , as defined before Lemma 36. As we observed, Q x is a subdirect product of R xw ×A v / α and by (S3) for P † we have Q x ∩(R xw † ×R v † / α ) is a subdirect product of R xw † and R v † / α ). For the relation Q y similar properties hold.
Consider the relation and S ′ = S ∩ B and S * = S/ µ •. It suffices to show that for some c ∈ R w † and e = B, such that (a, c) ∈ umax(R xw † ) and (b, c) ∈ umax(R yw † ) it holds (a, b, c, e, e) ∈ S ′ . Indeed, by the definition of Q x , Q y it means that (a, c) ∈ R xw ‡ and (b, c) ∈ R yw ‡ . As we observed above there is d ∈ R w † such that (a, d) ∈ R xw † , (b, d) ∈ R yw † , and the triple (a, b, d) extends to a tuple from S ′ . Note that as (a, b) ∈ umax(R xy ‡ ), d can be chosen such that (a, b, d) ∈ umax(pr x,y,w S ′ ). Thus, for some e 1 , e 2 ∈ B/ α we have a = (a, b, d, e 1 , e 2 ) ∈ S ′ . Since B v / α is a module and therefore is asconnected, a ∈ umax(S ′ ). On the other hand, by (R1) there is a solution ϕ of P † / µ • such that a ∈ ϕ(x), b ∈ ϕ(y), and ϕ(v) ∈ e. In other words, there are (a ′ , c ′ ) ∈ R xw ‡ peating the same argument we find a polynomial g of S satisfying the conditions (a)-(e) with c in place of a and using the (α, β v )-subtrace {e ′ , e} in coordinate position v 2 in place of {e 1 , e}. Then we conclude that for some c • ∈ Sg Aw (c • , g(c ′ )), such that c • c • is a thin affine edge it holds (a, b, c • , e, e) ∈ S and (a,

Lemma 37
The instance P ‡ satisfies (S3). That is, for every coherent set U the problem P ‡ /U is minimal. More precisely, for every s, R ‡ ∈ C ‡ , and every a ∈ R ‡ , there is a solution ϕ ∈ S ‡ /U such that ϕ(s) = a/ µ /U .
Proof: For a coherent set U and a constraint C = s, R ‡ it suffices only to check that tuples a ∈ R ′ ‡ are extendable to solutions of S ‡ /U , because R ‡ is generated by R ′ ‡ . For a constraint C ′ = s ′ , R ′ ∈ C, let Q C ′ denote the relation introduced before Lemma 36, and Q ′ C ′ = Q C ′ / µ /U . Let C 1 ⊆ C be the set of all constraints C ′ such that τ C ′ is maximal. Let also V = {x 1 , . . . , x n }, v = x i , s = (x 1 , . . . , x k ), and C 1 = {C 1 , . . . , C ℓ }, C j = s j , R j . Consider the relation . Let a ∈ R ′ ‡ and a ′ = a/ µ /U . It suffices to show that for some c ∈ pr x k+1 ,...,xn S † /U and e = B such that (a ′ , c) ∈ umax(S † /U ) it holds (a ′ , c, e, . . . , e) ∈ T ′ .
By construction there is a solution ϕ of P † / µ • (recall that this problem is Since a/ µ • ∈ umax(R † / µ • ), ϕ can be chosen from umax(S • † ). The existence of ϕ also means that for any C * = s * , R * ∈ C there is b C * ∈ R * ‡ such that b C * / µ • = ϕ(s * ). Again, b C * can be chosen from umax(R * † ). We show that there exists a solution ψ ∈ S † /U such that ψ(s) = a ′ and for every C * = s * , R * ∈ C 1 it holds (ψ(s * ), b ′ C * ) ∈ τ C * , where we use b ′ C * to denote b C * / µ /U . In other words, ψ ∈ S ‡ /U , as required. By the definition of Q Cj there exists e j ∈ B v / α such that (b Cj , e j ) ∈ Q Cj , and so (b ′ Cj , e j ) ∈ Q ′ Cj .
By (S3) for P † there is σ ∈ umax(S † /U ) with σ(s) = a ′ . Choose one for which condition (1) is true for a maximal number of constraints from C 1 . Suppose that (1) does not hold for C j = s * , R * ∈ C. Using the solution ϕ of P † / µ • we will construct another solution σ 0 ∈ S † /U such that (1) for σ 0 is true for all constraints it is true for σ, and is also true for C j .
By the definition of the congruences µ • z and Lemma 32(2) for every z ∈ V the interval (α, β v ) can be separated from (0 z , µ • z ) or the other way round. Therefore, by Lemma 24 there exists an idempotent polynomial f of T satisfying the following conditions: (a) f is B-preserving; (b) f (A v / α ) in the coordinate v j position of T is an (α, β v )-minimal set; and (c) f (µ • xq Bx q ) ⊆ 0 xq for q ∈ [n]. Since {e, e j } is a (α, β v )-subtrace of A v / α , as B v / α is a module, and (σ, e 1 , . . . , e ℓ ) ∈ umax(T ′ ), by Lemma 24 for T the polynomial f can be chosen such that The appropriate restrictions of f are also polynomials of Q ′ Cq and R ′ for each q ∈ [ℓ] and C ′ = s ′ , R ′ ∈ C. By (c) for any C ) for each w ∈ s • ∩ s • . This means that σ 0 = f (ϕ) is properly defined by setting σ 0 (w) = f (b ′ C • [w]) for any w ∈ V and C • = s • , R • ∈ C such that w ∈ s • . Also, for any constraint C q ∈ C 1 for which (1) holds for σ, it also holds for σ 0 , as f (σ(s q )) = σ(s q ) and so σ 0 (s j ) τC j ≡ b ′ Cj , that is, (1) holds for C j as well. The mapping σ 0 satisfies many of the desired properties, and it is a solution of P /U because σ 0 (s • ) ∈ R • for each C • = s • , R • ∈ C. However, it is not necessarily a solution of P † /U , and so we need to make one more step. To convert σ 0 into a solution of P † /U consider c = (σ, e, . . . , e) and d = (σ 0 , f 1 (e), . . . , f ℓ (e)). Note that the action of the polynomial f in coordinate positions v r of T may differ, we reflect it by using subscripts in the tuple d. In the subalgebra of T generated by c, d take c ′ = (ψ, e ′ 1 , . . . , e ′ ℓ ) such that cc ′ is a thin affine edge and c ′ [v j ] = e ′ j = f j (e) = e. For every C • = s • , R • ∈ C the relation R • † is polynomially closed in R • by (S5). Since σ(s • )ψ(s • ) is a thin affine edge in the subalgebra generated by σ(s • ), σ 0 (s • ), and σ 0 (s • ) is the image of b ′ C • ∈ R • † / µ /U under f , we get ψ(s • ) ∈ R • † / µ /U , as well. Thus, ψ is a solution of P † /U . Since σ(s) = σ 0 (s) = a ′ , the same holds for ψ(s). Also, for any constraint C q ∈ C 1 for which σ satisfies (1) so does σ 0 , and therefore ψ. Finally, by construction c ′ [v j ] = e, which means that (1) holds for C j as well. A contradiction with the choice of σ. ✷ 9 Proof of Theorem 12: non-affine factors In this section we consider Case 2 of tightening instances: for every v ∈ V and every α ∈ Con(A v ) with α ≺ β v it holds typ(α, β v ) = 2. Let P = (V, C) be a (2,3)-minimal and block-minimal instance with subdirectly irreducible domains, β = (β v ∈ Con(A v ) | v ∈ V ) and B = (B v | B v is a β v -block, v ∈ V ). Let also P † = (V, C † ) be a (β, B)-compressed instance, and for C = s, R ∈ C there is C † = s, R † ∈ C † . We select v ∈ V and α ∈ Con(A v ) with α ≺ β v , typ(α, β v ) = 2, and an α-block B ∈ B v / α such that B is as-maximal in R v † / α . By (S6) for P † for any C = s, R ∈ C with v ∈ s, the α-block B is also as-maximal in pr v (R ∩ B)/ α . In particular, it is maximal in B v / α = (R v ∩ B v )/ α . We show how P † can be transformed to a (β ′ , B ′ )-compressed instance such that β ′ w ≤ β w , B ′ w ⊆ B w for w ∈ V , and β ′ v = α, B ′ v = B. By Lemma 23 if R v † / α contains a nontrivial as-component, there is a coherent set associated with the triple (v, α, β v ). Let W = W (v, α, β v , β) in this case; note that (v, α, β v ) ∈ W ′ , because (α : β v ) = 1 v by Lemma 19 (2). Let also S † /U denote the set of solutions of P † /U for a coherent set U .

Lemma 38
If B v / α contains a nontrivial as-component, then for every w ∈ W there is a congruence α w ∈ Con(A w ) with α w < β w , and such that R vw † is aligned with respect to (α, α w ), that is, for any (a 1 , a 2 ), (b 1 , b 2 ) ∈ R vw † , a Proof: It suffices to show that the link congruences lk 1 , lk 2 of Q = R vw viewed as a subdirect product of A v × A w are such that β v ∧ lk 1 ≤ α and β w ∧ lk 2 < β w . Since w ∈ W there are γ, δ ∈ Con(A w ) such that γ ≺ δ ≤ β w and (α, β v ) and (γ, δ) cannot be separated. By Lemmas 19,27 it follows that β v ∧ lk 1 ≤ α and lk 2 ∧ δ ≤ γ. We set α w = β w ∧ lk 2 < β w . ✷ Let P ‡ = (V, C ‡ ) be constructed as follows.
(R) Let P ′ be the problem obtained from P † by adding extra constraint {v}, B . Let P ‡ be the problem obtained from P ′ by establishing (2, 3)-minimality, and the minimality of P ‡ /U for every non-central coherent set U .
Let Z be the set of variables w such that there is a congruence α w < β w such that R wv † / α is the graph of a mapping π w : R w † → R v † / α and α w is its kernel. For instance, if B belongs to a nontrivial as-component, then Z = W . For w ∈ U set β ′ w = α w , B ′ w = π −1 (B). For the remaining variables w set β ′ w = β w , Lemma 39 P ‡ satisfies condition (S5). In other words, for every C = s, R ∈ C, the relation R ‡ is polynomially closed in R.
Proof: Condition (S5) holds for P † . The instance P ‡ is obtained from P † by adding an extra constraint (whose relation is polynomially closed in A v ) and establishing various sorts of minimality. This means that every R ‡ is obtained through a pp-formula of polynomially closed relations. By Lemma 25 it is polynomially closed in R as well. ✷ Condition (S4) follows from Lemma 22 by the choice of β ′ v , B and (S6) for P † . The following two lemmas show that the constraints of P ‡ are not empty. We do it by identifying a set of tuples in every constraint relation that withstand the propagation algorithms. We start with constructing such sets for (2, 3)-minimality. Set Pick C = s, R ∈ C. We make use of the following property of R † : for any w, u ∈ s∩Z and any a ∈ R † , if a[w] ∈ B ′ w then a[u] ∈ B ′ u . We prove the claim in three steps. First, we will show that for every C = s, R ∈ C the relation R ′′ = R † ∩ x∈s T x is as-closed (not weakly as-closed!) in R ′ = R † ∩ B ′ . Second, we use Lemma 25 to conclude that R ‡ is as-closed in R ′′ . Third, we conclude that this implies that R ‡ is weakly as-closed in R ∩ B ′ .
For the first step, note that it suffices to show that T x is as-closed in pr x R ∩ B ′ x for x ∈ s. Depending on the case of the Congruence Lemma 26 that holds for R xv † / α and whether or not B belongs to a nontrivial as-component E, either umax(T x ) = umax(T ′x ), where or T x = B ′ x . In both cases the claim holds. The second step is immediate by Lemma 25. For the third step, if a ∈ umax(pr w R ‡ ) ⊆ umax(pr w (R ∩ B ′ )) and b ∈ pr w (R ∩ B ′ ) are such that a ⊑ as b for w ∈ s, then let a ∈ R ‡ with a = a[w]. Since a ∈ R † , by (S6) for R † , b ∈ pr w R † , and therefore b = b[w] for some b ∈ R † . As a ⊑ as b, the tuple b can be chosen such that a ⊑ as b in R † . Moreover, as we observed above, b ∈ R ′ . This means, by the second step, that b ∈ R ‡ , confirming the claim. ✷