[Rule] SET SPLITTING to BETWEENNESS

[isPANN]

Source: SET SPLITTING
Target: BETWEENNESS
Motivation: Establishes NP-completeness of BETWEENNESS via polynomial-time reduction from SET SPLITTING (hypergraph 2-colorability). This is the original transformation given by Opatrný (1979). Since Set Splitting is NP-complete (via NAE3SAT), this places the Betweenness ordering problem in NP-complete as well.

Reference: Garey & Johnson, Computers and Intractability, A12 MS1

GJ Source Entry

[MS1] BETWEENNESS
INSTANCE: Finite set A, collection C of ordered triples (a,b,c) of distinct elements from A.
QUESTION: Is there a one-to-one function f: A→{1,2,...,|A|} such that for each (a,b,c) ∈ C, we have either f(a) < f(b) < f(c) or f(c) < f(b) < f(a)?
Reference: [Opatrný, 1978]. Transformation from SET SPLITTING.

Reduction Algorithm

Summary:
Given a Set Splitting instance (S, C) where S = {s_1, ..., s_n} is a finite set and C = {c_1, ..., c_m} is a collection of subsets of S, construct a Betweenness instance as follows (following the construction in Opatrný 1979):

1. Elements: The set A of elements to be ordered consists of:

   • Two elements for each element s_i ∈ S: a "positive" copy s_i^+ and a "negative" copy s_i^−. These will encode the partition assignment.
   • Two special "pole" elements: p and q. In any valid ordering, these poles anchor the partition: elements placed between p and q on one side correspond to S_1, and elements on the other side correspond to S_2.
   • Additional auxiliary elements as needed for each subset constraint.

   Total: |A| = 2n + 2 + (auxiliary elements per subset).

2. Betweenness triples for complementarity: For each element s_i ∈ S, add triples that force s_i^+ and s_i^− to be on opposite sides of the ordering relative to the poles p, q. Specifically, add the triple (p, s_i^+, q) or equivalent constraints so that each s_i is assigned to exactly one partition.

3. Betweenness triples for subset constraints: For each subset c_j = {s_{j_1}, ..., s_{j_k}} ∈ C, construct triples that enforce the constraint "not all elements of c_j are on the same side." This is done by creating auxiliary elements and triples that are satisfiable if and only if at least one element of c_j is in S_1 and at least one is in S_2.

4. Correctness: A valid linear order of A satisfying all betweenness triples exists if and only if there is a partition of S into S_1, S_2 such that no subset in C is monochromatic.

5. Solution extraction: Given a satisfying linear order f of A, determine the partition: for each s_i ∈ S, if s_i^+ appears between the poles (i.e., f(p) < f(s_i^+) < f(q) or f(q) < f(s_i^+) < f(p)), assign s_i to S_1; otherwise assign s_i to S_2. The betweenness constraints guarantee that the resulting partition splits every subset in C.

Key invariant: The construction encodes the binary partition choice (S_1 vs S_2) as the relative position of element copies with respect to two poles, and encodes the "not all same" constraint for each subset as betweenness constraints on auxiliary elements.

Note: The full details of Opatrný's construction are given in: J. Opatrný, "Total ordering problem," SIAM Journal on Computing, 8(1):111–114, 1979. The construction is polynomial but somewhat involved, using O(n + m) elements and O(n + mk) triples where k is the maximum subset size.

Size Overhead

Symbols:

• n = universe_size (|S|, number of elements in Set Splitting instance)
• m = num_subsets (|C|, number of subsets)
• k = maximum subset size

Target metric (code name)	Polynomial (using symbols above)
num_elements	O(n + m)
num_triples	O(n + m * k)

Derivation: Each element of S contributes O(1) elements to A (positive/negative copies plus the two poles). Each subset contributes auxiliary elements and O(k) triples, where k is the subset size. The exact constants depend on the specific gadget construction from Opatrný's paper.

Validation Method

• Closed-loop test: construct a Set Splitting instance, reduce to Betweenness, solve Betweenness with BruteForce, extract the partition from the ordering, verify every subset in C is split
• Check that a splittable instance yields a valid betweenness ordering
• Check that a non-splittable instance yields no valid ordering
• Verify solution extraction: the partition derived from the ordering must split all subsets

Example

Source instance (Set Splitting):
Universe S = {0, 1, 2, 3, 4} (5 elements)
Collection C:

• c_0 = {0, 1, 2}
• c_1 = {2, 3, 4}
• c_2 = {0, 3, 4}
• c_3 = {1, 2, 3}

Satisfying partition: S_1 = {0, 2, 4}, S_2 = {1, 3}

• 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, 3, 4}: 0 ∈ S_1, 3 ∈ S_2 → split ✓
• c_3 = {1, 2, 3}: 2 ∈ S_1, 1 ∈ S_2 → split ✓

Target instance (Betweenness):
The full Betweenness instance constructed via Opatrný's reduction would involve 2×5 + 2 = 12 core elements (positive/negative copies of each element plus two poles p, q) and additional auxiliary elements per subset, with betweenness triples encoding the complementarity and splitting constraints. The exact construction is detailed in the original paper.

A valid linear ordering of the Betweenness instance would encode the partition S_1 = {0, 2, 4}, S_2 = {1, 3} through the relative positions of element copies with respect to the poles.

References

• [Opatrný, 1978]: [Opatrny1978] J. Opatrný (1979). "Total ordering problem". SIAM Journal on Computing, 8(1):111–114. (Note: G&J cite as 1978, likely referencing a preprint; the journal publication appeared in 1979.)

[GiggleLiu]

Implemented in PR #1010.