Set splitting problem

Set splitting shown on a hypergraph. The vertices make up the set S, and the edges make up the family of subsets F. The vertices are colored such that every edge has at least one vertex of each color (in this case, red and green).

In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.