3-OCC-MAX SAT np-complete?

Question

Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this problem, but I couldn't find it.

Answer 1

This problem is NP-complete. It is easy to see that it is in NP (guessing a model; check it in polynomial time).

First Attempt (Failure)

To show NP-hardness, I propose the following construction:

Consider a 3-SAT instance F over n variables. Consider a clause [L1, L2, L3]. Define fresh variables p1, p2, p3. Define Li equivalent to pi. Afterwards, replace the original clause using the fresh variables.

This results in clauses of the form:

[p1, p2, p3]
[-p1, L1]
[-L1, p1]
[-p2, L2]
[-L2, p2]
[-p3, L3]
[-L3, p3]

Do this for all clauses and always use fresh variables.

Note that the variables p1 to p3 are used exactly three times, whereas L1 till L3 are used twice. This construction is polynomial.

EDIT: I currently see that this is not a valid solution yet: The original literals may exceed the maximum occurence of 3.

Second Attempt

The idea is to use fresh variables for every apperance of a literal.

Let M be the number of appearences of variables in the 3SAT formula (this can be improved). For every atom A in the 3SAT CNF, add the following to the resulting the 3-OCC-MAX SAT formula:

q0 <- A
q1 <- q0
q2 <- q1
q3 <- q2     
q4 <- q3
...
q_M <- q_M-1
q_M+1 <- q_M
q0 <- q_M+1

Do the same for the occurences of -A.

p0 <- -A
p1 <- p0
p2 <- p1
p3 <- p2     
p4 <- p3
...
p_M <- p_M-1
p_M+1 <- p_M
p0 <- p_M+1

Furthermore, add the following to ensure that either the q-row or the p-row is true.

-p0 <- qM+1
-q0 <- pM+1

Now, add the clauses of the original 3SAT CNF, in which the n-th occurence of the literal L is replaced by qn. There is no "0-th occurence", i.e. we start counting by 1; therefore q0 and p0 as well as qM and pM are not used in this context. Note that A and -A appears 2x, the variable p0, q0, p_M+1, q_M+1 three times and the variables p_i, q_i, where i is between 1 and M at most three times.