I am wondering about the complexity of the following SAT related problem:
Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties:
- The intersection of any pair of different clauses only contains 1 variable.
- Every variable is only contained in one intersection. So every variable appears at most in two different clauses.
For example for $k=3$ : $(x \vee y \vee z)\wedge(y \vee u \vee w)\wedge (x \vee w \vee v)$ is a valid formula.
Is checking the satisfiability of this problem still NP-complete like 3-SAT? My gut tells me that the heavy restriction on the form may made it easier to solve this problem, but I'm not sure.