Consider the variant of the 3SAT problem with the following restrictions:
Each clause has 2 or 3 literals.
Each pair of 3-literal clauses have at most one common variable.
What is the complexity of this SAT problem?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityConsider the variant of the 3SAT problem with the following restrictions:
Each clause has 2 or 3 literals.
Each pair of 3-literal clauses have at most one common variable.
What is the complexity of this SAT problem?
The central insight is that you can use two $2$-variable clauses to make sure two variables have the same value. Let me abbreviate $(x \vee \neg y) \wedge (y \vee \neg x)$ with $x=y$. This allows the following reduction from 3SAT.
Given a 3SAT formula, copy the clauses to your reduction one by one. If you encounter a clause with a variable $x$ you've already seen twice, write the clause with a new variable $y$ instead of $x$ and add two $2$-variable clauses for $x=y$. Call the resulting formula $\phi$.
Formula $\phi$ satisfies requirements 1) and 2). Next, employ the same technique to ensure requirement 3). Walk through each pair of $3$-variable clauses of $\phi$ and for each pair which shares two variables $x$ and $y$, keep $x$ in one clause and in the other clause, change $x$ to $z$, and add $x=z$. An example:
$(x\vee y\vee h) \wedge (\neg x \vee \neg y \vee h) \mapsto (x\vee y\vee h) \wedge (\neg x \vee \neg z \vee h) \wedge (y=z)$
The resulting formula has as many $3$-variable clauses as the original and two $2$-variable clauses for each third or later repetition of a variable and then some more to satisfy requirement 3). Because the $2$-variable clauses ensure that $x=y$ so that your substitutions work, the resulting formula is satisfiable exactly when the original 3SAT formula was satisfiable. Its length is at most quadratic in the number of clauses of the original formula, so your problem is NP-Complete.
EDIT: I notice I interpreted your question to mean, a variable cannot appear in more than two $3$-variable clauses. The way it is formulated now, requirements 2) and 3) are equivalent. I hope you're not mad.