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.