An important property of acyclic instances is that they can efficiently be processed by dynamic programming. Indeed, according to Yannakakis'
algorithm [1]} (originally conceived in the equivalent context of evaluating acyclic Boolean conjunctive queries), they can be
evaluated by processing any of their join trees bottom-up, by performing upward semijoins between the constraint relations, thus keeping the
size of the intermediate result small. At the end, if the constraint relation associated with the root atom of the join tree is not empty, then
the CSP instance does admit a solution.
Therefore, the whole procedure is feasible in \(O(n\times r_{max}\times \log r_{max})\) ,
where \(n\)  is
the number of constraints and \(r_{max}\)  denotes the size of the largest constraint relation.
