Parameterized complexity of constraint satisfaction problems

We prove a parameterized analog of Schaefer’s Dichotomy Theorem: we show that for every finite boolean constraint family ℱ, deciding whether a formula containing constraints from ℱ has a satisfying assignment of weight exactly k is either fixed-parameter tractable (FPT) or W[1]-complete. We give a simple characterization of those constraints that make the problem fixed-parameter tractable. The special cases when the formula is restricted to be bounded occurrence, bounded treewidth, or planar are also considered: it turns out that in these cases the problem is in FPT for every constraint family ℱ.