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