# 3-SAT with atmost 3 variables and variable occuring once per clause

I've stumbled across this problem on CSES https://cses.fi/345/task/E/ and was wondering is it somehow reducible to 2-SAT with given constraints?

So, the problem states that you need to solve a 3-SAT given in a CNF form, albeit a special case, where:

1. Each clause has exactly 3 distinct variables
2. Each variable occurs at most 3 times in all clauses

I doubt that CSES would ask for a heuristic, solver like, approach but can't figure out how those new constraints help in creating a polynomial, possibly close to linear (due to size of input) solution.

Any help would be much appreciated :)

• Please edit your post to explain the problem in a self-contained way in the body of your post. We want the question to be understandable without having to click on an external link.
– D.W.
Apr 1, 2022 at 7:26
• Thanks for the reply, I have edited my question. Apr 1, 2022 at 13:11

Consider a bipartite graph $$G=(C+V, E)$$, where $$C$$ is the set of clauses and $$V$$ is the set of variables in the SAT instance. There is an edge $$(c,x)$$ with $$c \in C$$ and $$x \in V$$ if $$x$$ appears (possibly negated) in $$c$$.
Let $$S \subseteq C$$ and define $$N[S] = \{x \in V \mid \exists c \in C, (c,x) \in E \}$$. I claim that $$|N[S]| \ge |S|$$. Indeed, if we had $$|S| < |N[S]|$$ then the average number of occurrences of a variable in a clause in $$S$$ would be $$\frac{3 |S|}{|N[S]|} > 3$$, showing that some variable must appear at least $$4$$ times among the clauses in $$S$$.
Then, by Hall's theorem, $$G$$ admits a $$C$$-perfect matching. Consider any such matching and let $$x_c \in V$$ be the variable matched to $$c \in C$$. A satisfying assignment sets $$x_c$$ to true if $$x_c$$ is positive in $$c$$, and sets $$x_c$$ otherwise. All unmatched variables can be set arbitrarily.
A matching in a bipartite graph can be found in time $$O(m \sqrt{n})$$, where $$n$$ (resp. $$m$$) is the number of vertices (resp. edges) of $$G$$. In your case $$m = \Theta(n)$$, so the above simplifies to $$O(n^{3/2})$$.