# Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?

Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this paper that the problem of deciding whether one can delete at most $k$ clauses to make $\varphi$ satisfable, is fixed-parameter tractable, where $k$ is the parameter. My question is whether there are some work that generalize this result to other binary boolean CSP? (That is, to decide whether one can delete at most $k$ constraints to make some CSP instance satisfiable, parameterized by $k$) Or any negative results?

• I'm really curious as to what I'm missing here - isn't almost 2SAT trivially fixed-parameter tractable because there are only polynomially many sets of at most $k$ clauses for fixed $k$? – Dave Jul 20 '11 at 7:49
• @Dave there are about $O(n^k)$ sets of clauses, but fixed-parameter tractability doesn't allow $k$ to appear in the exponential part of the runtime. – Regularity Jul 20 '11 at 12:05