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''. Set Splitting is one of Computers and Intractability: A Guide to the Theory of NP-Completeness, Garey & Johnson's classical NP-complete problems. The problem is sometimes called Property B, hypergraph 2-colorability. Variants 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 problem and hence in Optimization_problem#NP_optimization_problem, NPO. 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 a ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]