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.


1 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.


Your Answer

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

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