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?
For what k is MAX-2-SAT-k NP-complete?
np hardness;sat;max2sat
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). LectureNotes In Computer Science, vol. 1644 (1999), pp. 200-209 :... for any $\epsilon > 0$ it is NP hard to decide whether aninstance of 3-OCC-MAX 2SATwith $2016 n$ clauses has a truth assignment that satisfiesat 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 :-)  