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?

  • $\begingroup$ 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$? $\endgroup$
    – Dave
    Jul 20, 2011 at 7:49
  • $\begingroup$ @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. $\endgroup$
    – Regularity
    Jul 20, 2011 at 12:05

1 Answer 1


To my knowledge classifying this CSP variant is wide open. You can express a few fixed-parameter tractable problems in the setting (e.g. d-Hitting Set is roughly the case where you have positive clauses of size at most d plus negative assignments; roughly means that the CSP problem is slightly more general but easily reduces back to d-HS, or at least weighted d-HS). Even for constraints that you can implement via existentially quantified 2-CNF formulas it is open what the complexity is. The problem is that when implementing constraints in this way, while they are 2-CNF, you pay only one to delete the whole thing. Hence even simple constraints which are just the conjunction of two others can be hard (I may have example + reference later).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.