[Model] SetSplitting #830
Description
Motivation
SET SPLITTING (P131) from Garey & Johnson, A3 SP4. A classical NP-complete problem useful for reductions. Also known as HYPERGRAPH 2-COLORABILITY: given a hypergraph, can its vertices be 2-colored so that no hyperedge is monochromatic?
- As source: R229 (→ Betweenness)
- As target: R73 (NAE3SAT →)
Definition
Name: SetSplitting
Reference: Garey & Johnson, Computers and Intractability, A3 SP4
Mathematical definition:
INSTANCE: Collection C of subsets of a finite set S.
QUESTION: Is there a partition of S into two subsets S_1 and S_2 such that no subset in C is entirely contained in either S_1 or S_2?
Variables
- Count: |S| (one binary variable per element of the universe S)
- Per-variable domain: {0, 1} — 0 means the element is assigned to S_1, 1 means it is assigned to S_2
- Meaning: x_i = 0 places element s_i in S_1, x_i = 1 places it in S_2. A valid partition requires that for every subset c ∈ C, c contains at least one element in S_1 and at least one element in S_2 (i.e., no subset is monochromatic).
Schema (data type)
Type name: SetSplitting
Variants: none
| Field | Type | Description |
|---|---|---|
universe_size |
usize |
Number of elements in the finite set S |
subsets |
Vec<Vec<usize>> |
Collection C of subsets of S, each subset given as a list of element indices (0-based) |
Complexity
- Best known exact algorithm: Brute-force enumeration over all 2^|S| partitions gives O*(2^n) where n = |S|. For the parameterized version (k-Set Splitting, where we ask if at least k subsets can be split), Lokshtanov and Saurabh (2009) give an O*(1.9630^k) deterministic algorithm using Measure & Conquer. For general decision, 2^n remains the baseline. The problem remains NP-complete even if all subsets have size ≤ 3, but is solvable in polynomial time if all subsets have size ≤ 2 (reduces to graph 2-colorability). [Lovász, 1973; Garey & Johnson, 1979; Lokshtanov & Saurabh, IWPEC 2009.]
Extra Remark
Full book text:
INSTANCE: Collection C of subsets of a finite set S.
QUESTION: Is there a partition of S into two subsets S_1 and S_2 such that no subset in C is entirely contained in either S_1 or S_2?
Reference: [Lovasz, 1973]. Transformation from NOT-ALL-EQUAL 3SAT. The problem is also known as HYPERGRAPH 2-COLORABILITY.
Comment: Remains NP-complete even if all c ∈ C have |c| ≤ 3. Solvable in polynomial time if all c ∈ C have |c| ≤ 2 (becomes GRAPH 2-COLORABILITY).
How to solve
- It can be solved by (existing) bruteforce. (Enumerate all 2^|S| bipartitions; check that no subset in C is monochromatic.)
- It can be solved by reducing to integer programming. (Binary ILP: x_i ∈ {0,1} for each element. For each subset c = {i_1,...,i_k} ∈ C, add constraints: Σ_{j∈c} x_j ≥ 1 and Σ_{j∈c} (1 - x_j) ≥ 1, ensuring c is not entirely in S_1 or S_2.)
- Other: (none known beyond brute force and ILP)
Reduction Rule Crossref
The direct SetSplitting → ILP rule will be bundled with this model issue per the CLAUDE.md exception for models with direct ILP solvability. The ILP formulation is described in the "How to solve" section above.
Example Instance
Input:
S = {0, 1, 2, 3, 4, 5} (universe of 6 elements)
Collection C of subsets:
- c_0 = {0, 1, 2}
- c_1 = {2, 3, 4}
- c_2 = {0, 4, 5}
- c_3 = {1, 3, 5}
Satisfying partition: S_1 = {0, 2, 5}, S_2 = {1, 3, 4}
- c_0 = {0, 1, 2}: 0 ∈ S_1, 1 ∈ S_2 → split ✓
- c_1 = {2, 3, 4}: 2 ∈ S_1, 3 ∈ S_2 → split ✓
- c_2 = {0, 4, 5}: 0 ∈ S_1, 4 ∈ S_2 → split ✓
- c_3 = {1, 3, 5}: 5 ∈ S_1, 1 ∈ S_2 → split ✓
All subsets contain elements from both S_1 and S_2, confirming this is a valid set splitting.
Configuration vector: [0, 1, 0, 1, 1, 0] (S_1=0, S_2=1)
Validation: Exhaustive enumeration confirms 18 feasible and 46 infeasible configurations out of 64 total (2^6). Both trivial all-zero and all-one configurations are infeasible. The example has sufficient constraint coverage for round-trip testing.