Since solving CSPs—and the above extensions—is an \(\mbox{\rm NP}\) -hard problem, much research has been spent to identify restricted classes over
which solutions can efficiently be computed. In this paper, structural decomposition methods are considered [1]}, which
identify tractable classes by exploiting the structure of constraint scopes as it can be formalized either as a hypergraph (whose nodes
correspond to the variables and where each group of variables occurring in some constraint induce a hyperedge) or as a suitable binary encoding
of such hypergraph. In particular, we focus on the structural methods based on the notions of (generalized) hypertree
width [2]}, [3]} and treewidth [4]}. In both cases, the underlying idea is that solutions to CSP instances that
are associated with acyclic (or nearly-acyclic) structures can efficiently be computed via dynamic programming, by incrementally processing the
structure according to some of its topological orderings.
