How to reduce 3-SAT to Set Splitting

Question

I've been reading through Garey & Johnson's "Computers and intractability", and a problem SP4 caught my attention. It is stated as following:

Given a collection $C$ of subsets of a finite set $S$, state if there's a partition into two subsets $S_1$ and $S_2$ such that no subset in $C$ is entirely contained in either $S_1$ or $S_2$?

The book says a Not-All-Equal-3SAT should be reduced to the stated problem to prove the NP-completeness sof the latter, but I can't seem to find a way. How to reduce NAE-3SAT to this problem?

Extra Question: how does one write an algorithm for such a partition?

I am aware about this discussion, but I couldn't find a link between reduction such as NAE-3SAT - 3COL - Set Splitting. If you can, please explain it.

Answer 1

Here is a reduction from NAE3SAT to your problem.

Given an instance $C_1 \lor \cdots \lor C_m$ of NAE3SAT, we construct an instance of your problem as follows:

• $S$ is the set of literals.
• $C$ consists of the sets $C_1,\ldots,C_m$ (considered as sets of literals) together with the sets $\{ x_i, \lnot x_i \}$ for each variable $x_i$.

A valid solution to this instance consists of a partition of $S$ into two sets $S_1,S_2$, which we can think of as a truth assignment to the variables: $x_i \in S_1$ iff $\lnot x_i \in S_2$. Think of the literals in $S_1$ as true. Then each clause must contain both true literals (literals in $S_1$) and false literals (literals in $S_2$), i.e., is should be satisfied as NAE.