One way of coping with the NP-hardness of the Uniform CSP is to identify
significantly large classes C of relational structures that are recognizable in
polynomial time, and such that, for each pair (A,B), with A belonging to C,
the problem instance CSP(A,B) is solvable in polynomial time.
There are different proposals in the literature for identifying such tractable
classes, exploiting the structural properties of the (hyper)graphs associated
to the CSP instances.
The talk describes the main notions and their relationship to database theory.
Successful applications of these structural decomposition methods are also
illustrated, as well as recent interesting advances in this field.
In particular, the presentation focuses on the notion of hypertree
decomposition and on some proposals for extending this method.
Finally, further structural approaches that do not require the explicit
computation of a hypergraph decomposition are illustrated and discussed.