# For what k is MAX-2-SAT-k NP-complete?

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?

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

• 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? Jan 8 '14 at 21:40
• @domotorp: you are right :-S ... "3-NAE-OCC MAX 2SAT"! :-) ... I'll edit the answer Jan 8 '14 at 21:46
• I wonder if the problem is also still PLS-complete. Jan 12 '14 at 12:38