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. It is an NP-complete problem. 
The optimization version of this problem is called Max Set Splitting and requires finding 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 
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.
The Weighted Set Splitting is a variant in which the subsets in F have weights and the objective is to maximize the total weight of the split subsets.
Read in another language
This page is available in 1 language