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, whether there exists a partition of S in two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is neither completely in S1 or S2. It is an NP-complete problem. [1]
The optimization version of this problem is called Max Set Splitting and requires to find the partition which maximizes the number of split elements of F. It is an APX-complete (and NP-hard) problem. The problem remains NP-hard even if all subsets in F contain the same fixed number of elements m greater than 1 [1]
The decision variant of Max Set Splitting, also called "Set Splitting" is stated as follows: given an integer k, whether there exists a partition of S which splits at least k subsets of F? If k taken to be a fixed parameter, then Set Splitting is fixed-parameter tractable, i.e., a polynomial algorithm exists for any fixed k. [1].