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. [1]
The decision variant of Max Set Splitting, also called "Set Splitting" is stated as follows: given an integer k, does there exist 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.[2]
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[3] (and NP-hard) problem. When each element of F is restricted to be of cardinality exactly k, the problem is called Max Ek-Set Splitting and remains NP-hard for k ≥ 2. For k=2, the problem reduces to the well-known Maximum cut. For k ≥ 4, Ek-Set Splitting is approximation resistant. That is, unless P=NP, there is no polynomial-time (factor) approximation algorithm which does essentially better than a random partition.[4]
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.
References
- ^ Garey, M.R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ "An FPT Algorithm for Set Splitting"
- ^ E. Petrank, "The hardness of approximation: Gap location", Computational Complexity, 4(1994), 133–157.
- ^ Template:Cite article