<p>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).</p>

CC BY-SA 3.0
2011-07-19T08:58:11.743Z
2011-07-19T08:58:11.743Z
Stefan Kratsch
<p>Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this <a href="http://arxiv.org/abs/0801.1300" rel="nofollow">paper</a> 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?</p>

CC BY-SA 3.0
2011-07-20T07:49:01.210Z
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
CC BY-SA 3.0
2011-07-20T12:05:16.243Z
@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
<parameterized-complexity><csp><fixed-parameter-tractable>
Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?
Regularity
# Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?

(Asked by: username_0 on 2011-07-18)

Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this [paper](http://arxiv.org/abs/0801.1300) 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?

**Tags:** parameterized-complexity, csp, fixed-parameter-tractable

> **Comments:**
> **username_1**: 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$?  
> **username_0**: @username_1 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.  

---

## 1 answers

### Answer by username_2 on 2011-07-19. Score: 8 | Accepted answer

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).


---

