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 S₁, S₂ such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S₁ or S₂. It is an NP-complete problem. ^[1]

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^[2] (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 ^[3]

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.^[3]

The Weighted Set Splitting is a variant in which the subsets in F have weights and the oblective is to maximize the total weight of the split subsets.

References

1. ^ Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. 
2. ^ E. Petrank, "The hardness of approximation: Gap location", Computational Complexity, 4(1994), 133–157.
3. ^ ^{a b} "An FPT Algorithm for Set Splitting"