4
$\begingroup$

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 :)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 1, 2022 at 7:26
  • $\begingroup$ Thanks for the reply, I have edited my question. $\endgroup$ Apr 1, 2022 at 13:11

1 Answer 1

3
$\begingroup$

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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.