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 Garey & Johnson's classical NP-complete problems.[1] The problem is sometimes called 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[2] problem and hence in 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 at least k subsets of F? The original formulation is the restricted case with k equal to the cardinality of F. The Set k-Splitting is fixed-parameter tractable, i.e., if k taken to be a fixed parameter, rather than a part of the input, then a polynomial algorithm exists for any fixed k. Dehne, Fellows and Rosamond presented an algorithm that solves it in time [math]\displaystyle{ O(f(k) n^c) }[/math] for some function f and constant c.[3]
When each element of F is restricted to be of cardinality exactly k, the decision variant is called Ek-set splitting and the optimization version max Ek-set splitting. For k > 2 the former remains NP complete, and for k ≥ 2 the latter remains APX complete.[4] 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.[5][6]
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.
Connection to other problems
Set splitting is special case of the not-all-equal satisfiability problem without negated variables. Additionally, Ek-set splitting equals non-monochromatic graph coloring of k-uniform hypergraphs. For k=2, the optimization variant reduces to the well-known maximum cut.[6]
References
- ↑ Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. 1979. ISBN 0-7167-1045-5.
- ↑ "The Hardness of Approximation: Gap Location". Computational Complexity (Springer) 4 (2): 133–157. 1994. doi:10.1007/BF01202286.
- ↑ Dehne, Frank; Fellows, Michael; Rosamond, Frances (2003). "An FPT Algorithm for Set Splitting". Graph Theoretic Concepts in Computer Science (WG2003), Lecture Notes in Computer Science. 2880. Springer. pp. 180–191. http://www.mrfellows.net/papers/FDR03_SetSplitting.pdf.
- ↑ "Coverings and Colorings of Hypergraphs". 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing. 1973.
- ↑ "Some Optimal Inapproximability Results". Journal of the ACM (Association for Computing Machinery) 48 (4): 798–859. 2001. doi:10.1145/502090.502098.
- ↑ 6.0 6.1 "Inapproximability Results for Set Splitting and Satisfiability Problems with no Mixed Clauses". Algorithmica (Springer) 38 (3): 451–469. 2003. doi:10.1007/s00453-003-1072-z.
 |  |
