  The constraint satisfaction problem (CSP) has important applications in
computer science and AI. In particular, infinite-domain CSPs have been
intensively used in subareas of AI such as spatio-temporal reasoning. Since
constraint satisfaction is a computationally hard problem, much work has been
devoted to identifying restricted problems that are efficiently solvable. One
way of doing this is to restrict the interactions of variables and constraints,
and a highly successful approach is to bound the treewidth of the underlying
primal graph. Bodirsky & Dalmau [J. Comput. System. Sci. 79(1), 2013] and Huang
et al. [Artif. Intell. 195, 2013] proved that CSP$(\Gamma)$ can be solved in
$n^{f(w)}$ time (where $n$ is the size of the instance, $w$ is the treewidth of
the primal graph and $f$ is a computable function) for certain classes of
constraint languages $\Gamma$. We improve this bound to $f(w) \cdot n^{O(1)}$,
where the function $f$ only depends on the language $\Gamma$, for CSPs whose
basic relations have the patchwork property. Hence, such problems are
fixed-parameter tractable and our algorithm is asymptotically faster than the
previous ones. Additionally, our approach is not restricted to binary
constraints, so it is applicable to a strictly larger class of problems than
that of Huang et al. However, there exist natural problems that are covered by
Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways
of generalising our results to larger families of languages. We also analyse
our algorithm with respect to its running time and show that it is optimal
(under the Exponential Time Hypothesis) for certain languages such as Allen's
Interval Algebra.
