CSPs can be solved in polynomial time when certain structural
parameters like treewidth or hypertree-width are bounded by a
constant. However, there is a trade-off between generality and
performance: larger bounds on the parameters yield worse time
complexities. It is desirable to pay for more generality only by a
constant factor in the running time, not by a larger degree of the
polynomial. Algorithms with such a uniform polynomial time complexity
are known as fixed-parameter algorithms. Parameterized complexity
offers tools for developing fixed-parameter algorithms and for
gathering strong theoretical evidence that certain problems are
inaccessible to fixed-parameter algorithms.
In this talk I will review some recent results on the parameterized
complexity of CSP with respect to combinations of the following
parameters: the treewidth of primal, dual, and incidence graphs, the
hypertree-width of constraint hypergraphs, the domain size, the
maximum arity of constraints, and the maximum size of overlaps of
constraint scopes. Furthermore, I will compare the parameterized
complexity of SAT and Boolean CSP. This is joint work with Marko
Samer.