\(\bullet \)
\({\it Var}^{\prime }={\it Var}\cup \lbrace S_1,...,S_q\rbrace \) , that is, also the constraint scopes of \( belong to the variables of the new problem;\)
\(\bullet \)
\(U^{\prime }=U\cup \lbrace \mathit {unsat}\rbrace \cup \lbrace  u_t \mid t\in r_i, \mbox{ for }1\le i\le q\rbrace \) ;
\(\bullet \)
\(=\lbrace  (\chi (v),r^{\prime }_v) \mid v\in T\rbrace \)  where the constraint relation \(r^{\prime }_v\)  is defined as follows.
Let \(\mu = |\chi (v)\cap {\it Var}|\) , and let \(U^\mu \)  denote the set of all possible tuples over the \(\mu \)  variables in \(\chi (v)\cap {\it Var}\) .
Let also \(S_{i_1},...S_{i_h}\)  be the scope-variables in \(\chi (v)\) . Then, for each tuple \(\theta \in U^\mu \) , the relation \(r^{\prime }_v\) 
contains all tuples \(\theta \cup \lbrace S_{i_1}/v_{i_1}\rbrace \cup \cdots \cup \lbrace  S_{i_h}/v_{i_h} \rbrace \) , where \(v_{i_j}\in U\)  (\(1\le j\le h\) ) is a value
for the scope-variable \(S_{i_j}\)  such that: \(v_{i_j}=u_t\)  if there is a tuple \(t\in r_{i_j}\)  conforming with \(\theta \) ; and \(v_{i_j}=\mathit {unsat}\) ,
if no such a tuple exists in \(r_{i_j}\) .
\(\bullet \)
\(w^{\prime }(X/u)=0\)  if \(u\ne \mathit {unsat}\) ; otherwise \(w^{\prime }(X/u)=1\) ,
that is, each constraint of \( that is not satisfied increases the cost of asolution by a unitary factor.\)
Note that this transformation is feasible in time exponential in the width of \(\langle T,\chi \rangle \)  only. Moreover, solutions of \(\mathcal {I}^{\prime }\)  with minimum
total cost precisely correspond to assignments over \(\mathcal {I}\)  minimizing the total number of violated constraints. In fact, the following can be
established.
Let \(\mathcal {I}=\langle {\it Var},U,\)  be a \({\mbox{Max-CSP}}\) instance with \(tw({\it inc}({\cal H}(\mathcal {I})))= k\) . Then, a solution to \(\mathcal {I}\)  can be computed in time
\(O(|{\it Var}|\times |U|^{k+1}\times \log |U|^{k+1})\) .
Conclusion and Discussion
In this paper, classes of tractable \({\mbox{CSOP}}\) , \({\mbox{WCSP}}\) , and \({\mbox{Max-CSP}}\)  instances are singled out by overviewing and proposing solution approaches
applicable to instances whose hypergraphs have bounded (generalized) hypertree width, or whose incidence graphs have bounded treewidth. The
techniques described in this paper are mainly based on Algorithm ComputeOptimalSolution, which has been designed to optimize costs
expressed as rational numbers and combined via the summation operation. However, it is easily seen that it remains correct if costs are
specified over an arbitrary totally ordered monoid structure, where some binary operation \(\oplus \)  (in place of standard summation) is used in
order to combine costs, provided it is commutative, associative, closed, and that it verifies identity and monotonicity. It follows that all
tractable classes of \({\mbox{CSOP}}\) , \({\mbox{WCSP}}\) , and \({\mbox{Max-CSP}}\)  instances identified in this paper remain tractable in such extended scenarios, which
indeed emerge with valued CSPs (see, e.g., [1]}).
