Set splitting problem

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.

The set k-splitting problem is stated as follows: given S, F, and an integer k, does there exist a partition of S which splits at least k subsets of F?

The original formulation is the restricted case with k equal to the cardinality of F. The Set k-Splitting is fixed-parameter tractable, i.e., if k taken to be a fixed parameter, rather than a part of the input, then a polynomial algorithm exists for any fixed k. Dehne, Fellows and Rosamond presented an algorithm that solves it in time

Set splitting is special case of the not-all-equal satisfiability problem without negated variables.

Additionally, Ek-set splitting equals non-monochromatic graph coloring of k-uniform hypergraphs.

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).
E k -set splitting, where k = 3. The "E" denotes that, on top of having k colors, each edge must contain exactly k vertices.