# 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.

## 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 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 $O(f(k)n^{c})$ for some function f and constant c.

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. 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.

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.