Set splitting problem
From Wikipedia, the free encyclopedia
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[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.
[edit] References
- ^ 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.
- ^ E. Petrank, "The hardness of approximation: Gap location", Computational Complexity, 4(1994), 133–157.
- ^ a b "An FPT Algorithm for Set Splitting"
