{'fraction_non_alphanumeric': 0.04456851096318565, 'fraction_numerical': 0.006155608045236562, 'mean_word_length': 4.28283337534661, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On The Power of Tree Projections: Structural Tractability of Enumerating CSP Solutions

The problem of deciding whether CSP instances admit solutions has been deeply studied in the literature, and several structural tractability results have been derived so far. However, constraint satisfaction comes in practice as a computation problem where the focus is either on finding one solution, or on enumerating all solutions, possibly projected to some given set of output variables. The paper investigates the structural tractability of the problem of enumerating (possibly projected) solutions, where tractability means here computable with polynomial delay (WPD), since in general exponentially many solutions may be computed. A general framework based on the notion of tree projection of hypergraphs is considered, which generalizes all known decomposition methods. Tractability results have been obtained both for classes of structures where output variables are part of their specification, and for classes of structures where computability WPD must be ensured for any possible set of output variables. These results are shown to be tight, by exhibiting dichotomies for classes of structures having bounded arity and where the tree decomposition method is considered.


Constraint Satisfaction and Decomposition Methods
Constraint satisfaction is often formalized as a homomorphism problem that takes as input two finite relational structures A (modeling variables and scopes of the constraints) and B (modeling the relations associated with constraints), and asks whether there is a homomorphism from A to B. Since the general problem is NP-hard, many restrictions have been considered in the literature, where the given structures have to satisfy additional conditions. In this paper, we are interested in restrictions imposed on the (usually said) left-hand structure, i.e., A must be taken from some suitably defined class A of structures, while B is any arbitrary structure from the class "−" of all finite structures. 1 Thus, we face the so-called uniform constraint satisfaction problem, shortly denoted as CSP(A, −), where both structures are part of the input (nothing is fixed).
The decision problem CSP(A, −) has intensively been studied in the literature, and various classes of structures over which it can be solved in polynomial time have already been singled out (see [6,11,18,1], and the references therein). These approaches, called decomposition methods, are based on properties of the hypergraph H A associated with each structure A ∈ A. In fact, it is well-known that, for the class A a of all structures whose associated hypergraphs are acyclic, CSP(A a , −) is efficiently solvable by just enforcing generalized arc consistency (GAC)-roughly, by filtering constraint relations until every pair of constraints having some variablesX in common agree onX (that is, they have precisely the same set of allowed tuples of values on these variablesX).
Larger "islands of tractability" are then identified by generalizing hypergraph acyclicity. To this end, every decomposition method DM associates with any hypergraph H A some measure w of its cyclicity, called the DM-width of H A . The tractable classes A of instances (according to DM) are those (with hypergraphs) having bounded width, that is, whose degree of cyclicity is below some fixed threshold. For every instance A in such a class A and every structure B, the instance (A, B) can be solved in polynomial-time by exploiting the solutions of a set of suitable subproblems, that we call views, each one solvable in polynomial-time (in fact, exponential in the-fixed-width, for all known methods). In particular, the idea is to arrange some of these views in a tree, called decomposition, in order to exploit the known algorithms for acyclic instances. In fact, whenever such a tree exists, instances can be solved by just enforcing GAC on the available views, even without computing explicitly any decomposition. This very general approach traces back to the seminal database paper [10], and it is based on the graph-theoretic notion of tree-projection of the pair of hypergraphs (H A , H V ), associated with the input structure A and with the structure V of the available views, respectively (tree projections are formally defined in Section 2).
For instance, assume that the fixed threshold on the width is k: in the generalized hypertree-width method [13], the available views are all subproblems involving at most k constraints from the given CSP instance; in the case of treewidth [21], the views are all subproblems involving at most k variables; for fractional hypertree-width, the views are all subproblems having fractional cover-width at most k (in fact, if we require that they are computable in polynomial-time, we may instead use those subproblems defined in [19] to compute a O(k 3 ) approximation of this notion).
Note that, for the special case of generalized hypertree-width, the fact that enforcing GAC on all clusters of k constraints is sufficient to solve the given instance, without computing a decomposition, has been re-derived in [5] (with proof techniques different from those in [10]). Moreover, [5] actually provided a stronger result, as it is proved that this property holds even if there is some homomorphically equivalent subproblem having generalized hypertree-width at most k. However, the corresponding only if result is missing in that paper, and characterizing the precise power of this GAC procedure for the views obtained from all clusters of k constraints (short: k-GAC) remained an open question. For any class A of instances having bounded arity (i.e., with a fixed maximum number of variables in any constraint scope of every instance of the class), the question has been answered in [2]: ∀A ∈ A, k-GAC is correct for every right-hand structure B if, and only if, the core of A has tree width at most k (recall that treewidth and generalized hypertree-width identify the same set of bounded-arity tractable classes). In its full version, the answer to this open question follows from a recent result in [15] (see Theorem 2-bis).
In fact, for any recursively enumerable class of bounded-arity structures A, it is known that this method is essentially optimal: CSP(A, −) is solvable in polynomial time if, and only if, the cores of the structures in A have bounded treewidth (under standard complexity theoretic assumptions) [17]. Note that the latter condition may be equivalently stated as follows: for every A ∈ A there is some A ′ homomorphically equivalent to A and such that its treewidth is below the required fixed threshold. For short, we say that such a class has bounded treewidth modulo homomorphic equivalence.
Things with unbounded-arity classes are not that clear. Generalized hypertree-width does not characterize all classes of (arbitrary) structures where CSP(A, −) is solvable in polynomial time [18]. It seems that a useful characterization may be obtained by relaxing the typical requirement that views are computable in polynomial time, and by requiring instead that such tasks are fixed-parameter tractable (FPT) [9]. In fact, towards establishing such characterization, it was recently shown in [20] that (under some reasonable technical assumptions) the problem CSP(H), i.e., CSP(A, −) restricted to the instances whose associated hypergraphs belong to the class H, is FPT if, and only if, hypergraphs in H have bounded submodular width-a new hypergraph measure more general than fractional hypertreewidth and, hence, than generalized hypertree-width.
It is worthwhile noting that the above mentioned tractability results for classes of instances defined modulo homomorphically equivalence are actually tractability results for the promise version of the problem. In fact, unless P = NP, there is no polynomial-time algorithm that may check whether a given instance A actually belongs to such a class A. In particular, it has been observed by different authors [24,4] that there are classes of instances having bounded treewidth modulo homomorphically equivalence for which answers computable in polynomial time cannot be trusted. That is, unless P = NP, there is no efficient way to distinguish whether a "yes" answer means that there is some solution of the problem, or that A ∈ A.
In this paper, besides promise problems, we also consider the so-called no-promise problems, which seem more appealing for practical applications. In this case, either certified solutions are computed, or the promise A ∈ A is correctly disproved. For instance, the algorithm in [5] solves the no-promise search-problem of computing a homomorphism for a given CSP instance (A, B). This algorithm either computes such a homomorphism or concludes that H A has generalized hypertree-width greater than k.

Enumeration Problems
While the structural tractability of deciding whether CSP instances admit solutions has been deeply studied in the literature, the structural tractability of the corresponding computation problem received considerably less attention so far [4], though this is certainly a more appealing problem for practical applications. In particular, it is well-known that for classes of CSPs where the decision problem is tractable and a self-reduction argument applies the enumeration problem is tractable too [8,7]. Roughly, these classes have a suitable closure property such that one may fix values for the variables without going out of the class, and thus may solve the computation problem by using the (polynomial-time) algorithm for the decision problem as an oracle. In fact, for the non-uniform CSP problem, the tractability of the decision problem always entails the tractability of the search problem [7]. As observed above, this is rather different from what happens in the uniform CSP problem that we study in this paper, where this property does not hold (see [24,4], and Proposition 1), and thus a specific study for the computation problem is meaningful and necessary.
In this paper, we embark on this study, by focusing on the problem ECSP of enumerating (possibly projected) solutions. Since even easy instances may have an exponential number of solutions, tractability means here having algorithms that compute solutions with polynomial delay (WPD): An algorithm M solves WPD a computation problem P if there is a polynomial p(·) such that, for every instance of P of size n, M discovers if there are no solutions in time O(p(n)); otherwise, it outputs all solutions in such a way that a new solution is computed within O(p(n)) time from the previous one.
Before stating our contribution, it is worthwhile noting that there are different facets of the enumeration problem, and thus different research directions to be explored: (Which Decomposition Methods?) We considered the more general framework of the tree projections, where subproblems (views) may be completely arbitrary, so that our results are smoothly inherited by all (known) decomposition methods. We remark that this choice posed interesting technical challenges to our analysis, and called for solution approaches that were not explored in the earlier literature on traditional methods, such as treewidth. For instance, in this general context, we cannot speak anymore of "the core" of a structure, because different isomorphic cores may have different structural properties with respect to the available views. . We believe this is the more natural approach. Indeed, modeling real-world applications through CSP instances typically requires the use of "auxiliary" variables, whose precise values in the solutions are not relevant for the user, and that are (usually) filtered-out from the output. In these cases, computing all combinations of their values occurring in solutions means wasting time, possibly exponential time. Of course, this aspect is irrelevant for the problem of computing just one solution, but is crucial for the enumeration problem.
(Should classes of structures be aware of output variables?) This is an important technical question. We are interested in identifying classes of tractable instances based on properties of their left-hand structures, while right-hand structures have no restrictions. What about output variables? In principle, structural properties may or may not consider the possible output variables, and in fact both approaches have been explored in the literature (see, e.g., [17]), and both approaches are dealt with in this paper. In the former output-aware case, possible output variables are suitably described in the instance structure. Unlike previous approaches that considered additional "virtual" constraints covering together all possible output variables [17], in this paper possible output variables are described as those variables X having a domain constraint dom(X), that is, a distinguished unary constraint specifying the domain of this variable. Such variables are said domain restricted. In fact, this choice reflects the classical approach in constraint satisfaction systems, where variables are typically associated with domains, which are heavily exploited by constraint propagation algorithms. Note that this approach does not limit the number of solutions, while in the tractable classes considered in [17] only instances with a polynomial number of (projected) solutions may be dealt with. As far as the latter case of arbitrary sets of output variables is considered, observe that in general stronger conditions are expected to be needed for tractability. Intuitively, since we may focus on any desired substructure, no strange situations may occur, and the full instance should be really tractable.

Contribution
Output-aware classes of ECSPs: ECSP instances over arbitrary output variables: (1) We describe an algorithm that, on input (A, B, O), solves the no-promise enumeration problem. In particular, either all solutions are computed, or it infers that there exists no tree projection of H A w.r.t. H V (the hypergraph associated with the views defined according to DM). This algorithm generalizes to the tree projection framework the enumeration algorithm of projected solutions recently proposed for the special case of treewidth [4]. (2) Finally, we give some evidence that, for bounded arity classes of instances, we cannot do better than this. In particular, having bounded width tree-decompositions of the full structure seems a necessary condition for enumerating WPD. We speak of "evidence," instead of saying that our result completely answers the open question in [17,4], because our dichotomy theorem focuses on classes of structures satisfying the technical property of being closed under taking minors (in fact, the same property assumed in the first dichotomy result on the complexity of the decision problem on classes of graphs [16]).

Preliminaries: Relational Structures and Homomorphisms
A constraint satisfaction problem may be formalized as a relational homomorphism problem. A vocabulary τ is a finite set of relation symbols of specified arities. A relational structure A over τ consists of a universe A and an r-ary relation R A ⊆ A r , for each relation symbol R in τ . If A and A ′ are two relational structures over disjoint vocabularies, we denote by A⊎A ′ the relational structure over the (disjoint) union of their vocabularies, whose domain (resp., set of relations) is the union of those of A and A ′ .
A homomorphism from a relational structure A to a relational structure B is a mapping h : A → B such that, for every relation symbol R ∈ A, and for every tuple a 1 , . . . , a r ∈ R A , it holds that h(a 1 ), . . . , h(a r ) ∈ R B . For any set X ⊆ A, denote by h[X] the restriction of h to X. The set of all possible homomorphisms from A to B is denoted by A B , while A B [X] denotes the set of their restrictions to X.
An instance of the constraint satisfaction problem (CSP) is a pair (A, B) where A is called a lefthand structure (short: ℓ-structure) and B is called a right-hand structure (short: r-structure). In the classical decision problem, we have to decide whether there is a homomorphism from A to B, i.e., whether A B = ∅. In an instance of the corresponding enumeration problem (denoted by ECSP) we are additionally given a set In the constraint satisfaction jargon, the elements of A (the domain of the ℓ-structure A) are the variables, and there is a constraint C = ( a 1 . . . , a r , R B ) for every tuple a 1 . . . , a r ∈ R A and every relation symbol R ∈ τ . The tuple of variables is usually called the scope of C, while R B is called the relation of C. Any homomorphism from A to B is thus a mapping from the variables in A to the elements in B (often called domain values) that satisfies all constraints, and it is also called a solution (or a projected solution, if it is restricted to a subset of the variables).
Two relational structures A and A ′ are homomorphically equivalent if there is a homomorphism from A to A ′ and vice-versa

Decomposition Methods, Views, and Tree Projections
Throughout the following sections we assume that (A, B) is a given connected CSP instance, and we shall we shall seek to compute its solutions (possibly restricted to a desired set of output variables) by combining the solutions of suitable sets of subproblems, available as additional distinguished constraints called views.
Let A V be an ℓ-structure with the same domain as A. We say that A V is a view structure (short: v-structure) if -its vocabulary τ V is disjoint from the vocabulary τ of A; -every relation R AV contains a single tuple whose variables will be denoted by var (R AV ). That is, there is a one-to-one correspondence between views and relation symbols in τ V , so that we shall often use the two terms interchangeably; -for every relation R ∈ τ and every tuple t ∈ R A , there is some relation R t ∈ τ V , called base view, such that {t} = R AV t , i.e., for every constraint in A there is a corresponding view in A V . Let B V be an r-structure. We say that That is, every subproblem is not more restrictive than the full problem.
That is, any base view is at least as restrictive as the "original" constraint associated with it.
The following fact immediately follows from the above properties.
In fact, all structural decomposition methods define some way to build the views to be exploited for solving the given CSP instance. In our framework, we associate with any decomposition method DM a pair of polynomial-time computable functions ℓ-DM and r-DM that, given any CSP instance (A, B), is a legal r-structure. 2 For instance, for any fixed natural number k, the generalized hypertree decomposition method [12] (short: hw k ) is associated with the functions ℓ-hw k and r -hw k that, given a CSP instance (A, B), build the pair (ℓ-hw k (A), r -hw k (A, B)) where, for each subset C of at most k constraints from (A, B), there is a view R C such that: ) is the set of all variables occurring in C, and (2) the tuples in R r -hw k (A,B) C are the solutions of the subproblem encoded by C. Similarly, the tree decomposition method [21] (tw k ) is defined as above, but we consider each subset of at most k variables in A instead of each subset of at most k constraints.

Tree Projections for CSP Instances
In this paper we are interested in restrictions imposed on left-hand structures of CSP instances, based on some decomposition method DM. To this end, we associate with any ℓ-structure A a hypergraph H A = (A, H), whose set of nodes is equal to the set of variables A and where, for each constraint scope in R A , the set H of hyperedges contains a hyperedge including all its variables (no further hyperedge is in H). In particular, the v-structure A V = ℓ-DM(A) is associated with a hypergraph H AV = (A, H), whose set of nodes is the set of variables A and where, for each view R ∈ τ V , the set H contains the hyperedge var (R AV ). In the following, for any hypergraph H, we denote its nodes and edges by nodes(H) and edges(H), respectively. Example 1. Consider the ℓ-structure A whose vocabulary just contains the binary relation symbol R, and such that R A = { F, E , A, E , A, C , A, B , B, C , D, B , D, C }. Such a simple onebinary-relation structure may be easily represented by the directed graph in the left part of Figure 1, where edge orientation reflects the position of the variables in R. In this example, the associated hypergraph H A is just the undirected version of this graph. Let DM be a method that, on input A, builds the v-structure A V = ℓ-DM(A) consisting of the seven base views of the form R t , for each tuple t ∈ R A , plus the three relations R 1 , R 2 , and R 3 such that R AV Figure 1 also reports H AV . ⊳ A hypergraph H is acyclic iff it has a join tree [3], i.e., a tree JT (H), whose vertices are the hyperedges of H, such that if a node X occurs in two hyperedges h 1 and h 2 of H, then h 1 and h 2 are connected in JT (H), and X occurs in each vertex on the unique path linking h 1 and h 2 in JT (H).
For two hypergraphs H 1 and H 2 , we write H 1 ≤ H 2 iff each hyperedge of H 1 is contained in at least one hyperedge of H 2 . Let H 1 ≤ H 2 . Then, a tree projection of H 1 with respect to H 2 is an acyclic hypergraph H a such that H 1 ≤ H a ≤ H 2 . Whenever such a hypergraph H a exists, we say that the pair (H 1 , H 2 ) has a tree projection (also, we say that H 1 has a tree projection w.r.t. H 2 ). The problem of deciding whether a pair of hypergraphs has a tree projection is called the tree projection problem, and it has recently been proven to be NP-complete [14]. Note that all the (known) structural decomposition methods can be recast as special cases of tree projections, since they just differ in how they define the set of views to be built for evaluating the CSP instance. For instance, a hypergraph H A has generalized hypertree width (resp., treewidth) at most k if and only if there is a tree projection of H A w.r.t. H ℓ-hw k (A) (resp., w.r.t. H ℓ-tw k (A) ).
However, the setting of tree projections is more general than such traditional decomposition approaches, as it allows us to consider arbitrary sets of views, which often require more care and different techniques. As an example, we shall illustrate below that in the setting of tree projections it does not make sense to talk about "the" core of an ℓ-structure, because different isomorphic cores may differently behave with respect to the available views. This phenomenon does not occur, e.g., for generalized hypertree decompositions, where all combinations of k constraints are available as views.

CSP Instances and tp-Coverings
We complete the picture of our unifying framework to deal with decomposition methods for constraint satisfaction problems, by illustrating some recent results in [15], which will be useful to our ends. Let us start by stating some preliminary definitions.
has a tree projection. 3 For instance, it is easily seen that the variables {A, B, C} are tp-covered in the v-structure A V discussed in Example 1. In particular, note that the structure A ⊎ S {A,B,C} is associated with the same hypergraph H A ′ that has a tree projection w.r.t. H AV (cf. Example 3). Instead, the variables {B, C, D} are not tp-covered in A V .
Given a CSP instance (A V , B V ), we denote by GAC(A V , B V ) the r-structure that is obtained by enforcing generalized arc consistency on (A V , B V ).
The following result, proved in [15] for a different setting, states the precise relationship between generalized-arc-consistent views and tp-covered sets of variables.

Theorem 2. Let
A be an ℓ-structure, and let A V be a v-structure. The following are equivalent: (2) For every r-structure B, for every r-structure B V that is legal w.r.t. A V and (A, B), and for every relation Note that the result answered a long standing open question [10,23] about the relationship between the existence of tree projections and (local and global) consistency properties in databases [15]. In words, the result states that just enforcing generalized arc consistency on the available views is a sound and complete procedure to solve ECSP instances if, and only if, we are interested in (projected) solutions over output variables that are tp-covered and occur together in some available view. Thus, in these cases, all solutions can be computed in polynomial time. The more general case where output variables are arbitrary (i.e., not necessarily included in some available view) is explored in the rest of this paper.
We now leave the section by noticing that as a consequence of Theorem 2, we can characterize the power of local-consistency for any decomposition method DM such that, for each pair (A, B), each view in B V = r-DM(A, B) contains the solutions of the subproblem encoded by the constraints over which it is defined. For the sake of simplicity, we state below the result specialized to the well-known decomposition methods tw k and hw k . Theorem 2-bis. Let DM be a decomposition method in {tw k , hw k }, let A be an ℓ-structure, and let A V = ℓ-DM(A). The following are equivalent: (2) For every r-structure B, and for every relation Proof (Sketch). Preliminarily, it is easy to see that (2) in Theorem 2 may be equivalently stated as follows: (2') For every r-structure B, for every r-structure B V that is legal w.r.t. A V and (A, B) and such that The fact that (1) ⇒ (2) trivially follows from Theorem 2. We have to show that (2) ⇒ (1) holds as well. To this end, observe that if O is not tp-covered in ℓ-DM(A), by Theorem 2 (actually, (1) ⇒ (2 ′ )), we can conclude the existence of: (1) an r-structure B, (2) an r-structure B V that is legal w.r.t.
. The same line of reasoning applies to the tree decomposition method. ⊳ Note that if we consider decision problem instances (O = ∅) and the treewidth method (A V = ℓ-tw k (A)), from Theorem 2-bis, we (re-)obtain the nice characterization of [2] about the relationship between k-local consistency and treewidth modulo homomorphic equivalence. If we consider generalized hypertree-width (A V = ℓ-hw k (A)), we get the answer to the corresponding open question for the unbounded arity case, that is, the precise power of the procedure enforcing k-union (of constraints) consistency (i.e., the power of the algorithm for the decision problem described in [5]).

Enumerating Solutions of Output-Aware CSP Instances
The goal of this section is to study the problem of enumerating CSP solutions for classes of instances where possible output variables are part of the structure of the given instance. This is formalized by assuming that the relational structure contains domain constraints that specify the domains for such variables.

Definition 2. A variable
The set of all domain restricted variables is denoted by drv (A).

We say that an ECSP instance (A, B, O) is domain restricted if O ⊆ drv (A).
Of course, if it is not, then one may easily build in linear time an equivalent domain-restricted ECSP instance where an additional fresh unary constraint is added for every output variable, whose values are taken from any constraint relation where that variable occurs. We say that such an instance is a domain-restricted version of (A, B, O). Figure 2 shows an algorithm, named ComputeAllSolutions DM , that computes the solutions of a given ECSP instance. The algorithm is parametric w.r.t. any chosen decomposition method DM, and works as follows. Firstly, ComputeAllSolutions DM starts by transforming the instance (A, B, O) into a domain restricted one, and by constructing the views in (A V , B V ) via DM. Then, it invokes the procedure Propagate. This procedure backtracks over the output variables {X 1 , . . . , X m }: At each step i, it tries to assign a value to X i from its domain view, 4 and defines this value as the unique one available in that domain, in order to "propagate" such an assignment over all other views. This is accomplished by enforcing generalized arc-consistency each time the procedure is invoked. Eventually, whenever an assignment is computed for all the variables in O, this solution is returned in output, and the algorithm proceeds by backtracking again trying different values.

Tight Characterizations for the Correctness of ComputeAllSolutions DM
To characterize the correctness of ComputeAllSolutions DM , we need to define a structural property that is related to the one stated in Definition 1. Below, differently from Definition 1 where the set of output variables O is treated as a whole, each variable in O has to be tp-covered as a singleton set. Note that the above definition is purely structural, because (the right-hand structure) B plays no role there. In fact, we next show that this definition captures classes of instances where ComputeAllSolutions DM is correct.
. Thus, all values in the domain views associated with output variables occur in some solutions. This holds in particular for dom(X 1 ) that is empty if, and only if, A B0 = ∅, in which case the cycle is skipped and the algorithm immediately halts with an empty output. Assume now that this is not the case, so that activeValues = A B0 [{X 1 }] = ∅, and let a 1 be the chosen value at Step 3. Consider a new instance I 1 = (A, B 1 , O) where the domain constraint for X 1 contains the one value a 1 . From the above discussion it follows that A B1 = ∅, and clearly the solutions of I 1 are all and only those of I 0 that extend the partial solution a 1 . Moreover, it is easy to check that the r-structure B ′ V obtained after the execution of Step 7 is legal w.r.t. (A, B 1 ), and recall that nothing is changed in the pair (A, O), which is (still) tp-covered through DM. Therefore, when we call recursively call Propagate at Step 8 with i = 2, we are in the same situation as in the first call, but going to enumerate the solutions of I 1 .
At the end of this call, we just repeat this procedure with the next available value for X 1 , say a 2 , until all elements in activeValues = A B 0 [{X 1 }] have been considered (and propagated). ⊳ We now complete the picture by observing that Definition 3 also provides the necessary conditions for the correctness of ComputeAllSolutions DM . As in Theorem 2-bis, we state below the result specialized to the methods tw k and hw k .

Tight Characterizations for Enumerating Solutions with Polynomial Delay
We next analyze the complexity of ComputeAllSolutions DM . In the case where there is no solution, we claim that the r-structure B ′ V obtained by enforcing generalized arc consistency in the first invocation of Propagate (i.e., for i = 1) is empty. Indeed, since (A, O) is tp-covered through DM, then {X 1 } is tp-covered in A V -just compare Definition 1 and Definition 3. It follows that we can apply Theorem 2 on the set {X 1 } in order to conclude that, for

Theorem 5. Let
is empty, the above implies that GAC(A V , B V ) is empty too. Thus, ComputeAllSolutions DM invokes just once Propagate, where the only operation carried out is to enforce generalized arc consistency, which is feasible in polynomial time.
Consider now the case where A B [O] is not empty. Then, the first solution is computed after m recursive calls of the procedure Propagate, where the dominant operation is to enforce generalized arc consistency on the current pair (A V , B V ). In particular, by the arguments in the proof of Theorem 3, it follows that Propagate does not have to backtrack to find this solution: after enforcing generalized arc consistency at step i, any active value for X i is guaranteed to occur in a solution with the current fixed values for the previous variables X j , 1 ≤ j < i. Since GAC can be enforced in polynomial time, this solution can be computed in polynomial time as well.
To complete the proof, observe now that any solution is provided in output when Propagate is invoked for i = m. After returning a tuple of values a 1 , ..., a m , Propagate may need to backtrack to a certain index i ′ ≥ 1 having some further (different) value a i ′ to be processed, fix X i ′ with this value, propagate this assignment, and continue by processing variable X i ′ +1 . Thus, at most m invocations of Propagate are needed to compute the next solution, and no backtracking step may occur before we found it. Therefore, ComputeAllSolutions DM runs WPD. ⊳ By the above theorem and the definition of domain restricted variables, the following can easily be established. In the case of bounded arity structures and if the (hyper)tree width is the chosen decomposition method, it is not hard to see that the result in Corollary 1 is essentially tight. Indeed, the implication (2) ⇒ (1) in the theorem below easily follows from the well-known dichotomy for the decision version [17], which is obtained in the special case of ECSP instances without output variables (O = ∅). Actually, from an application perspective of this result, we observe that there is no efficient algorithm for the no-promise problem for such classes. In fact, the following proposition formalizes and generalizes previous observations from different authors about the impossibility of actually trusting positive answers in the (promise) decision problem [24,4].
We say that a pair (h, c) is a certified projected solution of (A, B, O) if, by using the certificate c, one may check in polynomial-time (w.r.t. the size of (A, B, O)) whether h ∈ A B [O]. E.g., any full solution extending h is clearly such a certificate. If O = ∅, h is also empty, and c is intended to be a certificate that (A, B) is a "Yes" instance of the decision CSP. Finally, we assume that the empty output is always a certified answer, in that it entails that the input is a "No" instance, without the need for an explicit certificate of this property. , otherwise, everything is acceptable. In particular, we do not pretend that M recognizes whether the above condition is fulfilled.
Then, we use M as an oracle procedure within a polynomial time algorithm that solves the 3colorability problem. Let G = (N, E) be any given graph, and assume w.l.o.g. that it contains a triangle {n 1 , n 2 }, {n 2 , n 3 }, and {n 3 , n 1 }. (Otherwise, select any arbitrary vertex n 1 of G and connect it to two fresh vertices n 2 and n 3 , also connected to each other. It is easy to check that this new graph is 3-colorable if, and only if, the original graph G is 3-colorable, as the two fresh vertices have no connections with the rest of the graph.) Build the (classical) binary CSP (A G , B 3c ) where the vocabulary contains one relation symbol R E , and the set of variables is Consider the treewidth method for k = 2, and compute in polynomial time the pair (A V , B V ) where A V = ℓ-tw 2 (A G ) and B V = r -tw 2 (B 3c ). In particular, observe that the hypergraph H AV contains a hyperedge {n i , n j , n l } for every triple of vertices of G.
It is well-known and easy to see that G is 3-colorable if, and only if, A B3c G = ∅, that is, if there is a homomorphism from A G to a triangle (indeed, B 3c is a triangle). Therefore, if G is 3-colorable, the triangle substructure A ′ such that R A ′ E = { n i , n j | {i, j} ⊂ {1, 2, 3} | i = j} is homomorphically equivalent to A G . Moreover, in this case the hypergraph consisting of the single hyperedge {n 1 , n 2 , n 3 } is a tree projection of H A ′ w.r.t. H AV , or, equivalently, the treewidth of A ′ is 2.
Now, run M on input (A G , B 3c , ∅) and consider its first output certificate c-say, for the sake of presentation, a full solution for the problem. Then check in polynomial time whether c is a legal certificate-in our exemplification, whether it encodes a solution of the given instance. If this is the case, we know that G is 3-colorable; otherwise, we conclude that G is not 3-colorable. Indeed, M must be correct on 3-colorable graphs, because there exists a tree projection of H A ′ (and thus of any core of A G -note that O = ∅ and thus there is no further requirement) w.r.t. H AV . Since all these steps are feasible in polynomial-time, we are done. ⊳

Enumerating Solutions over Arbitrary Output Variables
In this section we consider structural properties that are independent of output variables, so that tractability must hold for any desired sets of output variables. For this case, we are able to provide certified solutions WPD, which seems the more interesting notion of tractability for actual applications. Figure 3 shows the ComputeCertifiedSolutions DM algorithm computing all solutions of an ECSP instance, with a certificate for each of them. The algorithm is parametric w.r.t. any chosen decomposition method DM, and resembles in its structure the ComputeAllSolutions DM algorithm. The main difference is that, after having found an assignment a 1 , ..., a m for the variables in O, ComputeCertifiedSolutions DM still iterates over the remaining variables in order to find a certificate for that projected solution. Of course, ComputeCertifiedSolutions DM does not backtrack over the possible values to be assigned to the variables in {X m+1 , ..., X n }, since just one extension suffices to certify that this partial solution can be extended to a full one. Thus, we break the cycle after an element a i is picked from its domain and correctly propagated, for each i > m, so that in these cases we eventually backtrack directly to i = m (to look for a new projected solution).
Note that ComputeCertifiedSolutions DM incrementally outputs various solutions, but it halts the computation if the current r-structure B ′ V becomes empty. As an important property of the algorithm, even when this abnormal exit condition occurs, we are guaranteed that all the elements provided as output until this event are indeed solutions. Moreover, if no abnormal termination occurs, then we are guaranteed that all solutions will actually be computed. Correctness follows easily from the same arguments used for ComputeAllSolutions DM , by observing that, whenever (H A , H ℓ-DM(A) ) has a tree projection, the full set of variables A is tp-covered through DM.  (v 1,1 , v 1,2 , . . . , v 1,k2 ) of G. We have seen that its endpoints, which are grid-corners, are fixed. It is easy to check that h cannot map the path r 1 to any path that is longer than r 1 . However, r 1 is the shortest path connecting the fixed endpoints v 1,1 and v 1,k2 , and hence it must be mapped to itself. That is, h(X) = X for every element X occurring in r 1 , and thus, by the same reasoning, for every element X occurring in the last row, and in the first and the last columns of the grid. It follows that the endpoints v 2,1 and v 2,k2 of the second row r 2 are fixed as well, and we may apply the same argument to show that all elements occurring in r 2 are fixed, too. Eventually, row after row, we get that all elements of A are fixed, and thus the identity mapping is the only possible endomorphism for A, which entails that A is a core. ⊳ We also exploit the grid-based construction from [17], whose properties relevant to this paper may be summarized as follows.

Proposition 2 ([17]
). Let k ≥ 2 and K = k 2 , and let A be any τ -structure such that the (k × K)grid is a minor of the Gaifman graph of a core of A. For any given graph G, one can compute in polynomial time (w.r.t. G ) a τ -structure B A,G such that G contains a k-clique if, and only if, there is a homomorphism from A to B A,G .
We can now prove the necessity of bounded treewidth for tractability WPD. Proof. The fact that (1) ⇒ (2) holds follows by specializing Theorem 7 to the tree decomposition method. We next focus on showing that (2) ⇒ (1) also holds.
Let A be such a bounded-arity class of ℓ-structures closed under taking minors, and having unbounded treewidth. From this latter property, by the Excluded Grid Theorem [22] it follows that every grid is a minor of the Gaifman graph of some ℓ-structure in A. Moreover, because this class is closed under taking minors, every grid is actually the Gaifman graph of some ℓ-structure in A.
Assume there is a deterministic Turing machine M that is able to solve with polynomial delay any ECSP instance (A, B, O) such that A ∈ A. We show that this entails the existence of an FPT algorithm to solve the W[1]-hard problem p-CLIQUE, which of course implies FPT = W [1].
Let G be a graph instance of the p-CLIQUE problem, with the fixed parameter k ≥ 2. We have to decide whether G has a clique of cardinality k. We enumerate the recursively enumerable class A until we eventually find an ℓ-structure A whose Gaifman graph is the (k × K)-grid. Let τ be its vocabulary. Note that searching for this structure A depends on the fixed parameter k only (in particular, it is independent of G).
Let O ⊆ A be the variables at the four corners of this grid, and let A ′ be the extension of A such that, for every variable X ∈ O, the vocabulary τ ′ of A ′ contains the domain relation-symbol dom(X). Thus, the Gaifman graph of A ′ is the same (k × K)-grid as for A, but its four corners are domain-restricted in A ′ (O ⊆ drv (A ′ )). From Lemma 1, A ′ is a core.
Recall now the grid-based construction in Proposition 2: We can build in polynomial time (w.r.t. G ) a structure B ′ A ′ ,G such that there is a homomorphism from A ′ to B ′ A ′ ,G if, and only if, G has a clique of cardinality k.
Consider the ECSP instance (A, B, O) where A ∈ A by construction, and B is the restriction of B ′ A ′ ,G to the vocabulary τ . Thus, compared with B ′ A ′ ,G , the r-structure B may miss the domain constraint dom(X) for some output variable X ∈ O. It is easy to see that h is a homomorphism from A ′ to B ′ if, and only if, h is a homomorphism from A to B such that, for every X ∈ O, h(X) ∈ dom(X) B ′ A ′ ,G . Therefore, to decide whether such a homomorphism exists (and hence to solve the clique problem), we can just enumerate WPD the set of solutions A By combining the above ingredients, we got an FPT algorithm to decide whether G has a clique of cardinality k. ⊳