It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs in at most k clauses of the 2-CNF for some constant k. Can someone give me a good bound on k?

Can we suppose that every variable occurs at most twice negated or at most twice unnegated?


3-OCC-MAX 2SAT: given a CNF formula $\varphi$ in which each clause contains at most 2 literals and each variable appears in at most three clauses (counting together both positive and negative literals); does there exist an assignment that satisfies at least $k$ clauses?

In P. Berman, M. Karpinski, On some tighter inapproximability results (1998). Lecture Notes In Computer Science, vol. 1644 (1999), pp. 200-209 :

... for any $\epsilon > 0$ it is NP hard to decide whether an instance of 3-OCC-MAX 2SAT with $2016 n$ clauses has a truth assignment that satisfies at least $(2012 - \epsilon)n$ clauses.

As noted in the domotorp's comment, if a variable appers only positive or negative we can fix its value (satisfying and deleting all the clauses in which it appears); so we can assume that the 3 occurrences are not-all-equal ending up in a "3-NAE-OCC-MAX 2SAT" instance :-)

  • $\begingroup$ Nice, just what I wanted! Before I accept, why could we not reduce it? If a variable appeared only pos or neg, then we can fix its value, so we can suppose there are no such variables, right? $\endgroup$
    – domotorp
    Jan 8 '14 at 21:40
  • $\begingroup$ @domotorp: you are right :-S ... "3-NAE-OCC MAX 2SAT"! :-) ... I'll edit the answer $\endgroup$ Jan 8 '14 at 21:46
  • $\begingroup$ I wonder if the problem is also still PLS-complete. $\endgroup$ Jan 12 '14 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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