Source: 3-DIMENSIONAL MATCHING
Target: 3-PARTITION
Motivation: This is the classical reduction proving 3-PARTITION is NP-complete in the strong sense, originally due to Garey & Johnson (1975). It proceeds via an intermediate 4-partition (ABCD-partition) step: 3DM -> 4-partition -> 3-partition. The strong NP-completeness of 3-PARTITION makes it a powerful source for subsequent reductions to scheduling, bin packing, and resource allocation problems.
Reference: Garey & Johnson, Computers and Intractability, SP15, p.224
GJ Source Entry
[SP15] 3-PARTITION
INSTANCE: Set A of 3m elements, a bound B∈Z^+, and a size s(a)∈Z^+ for each a∈A such that B/4<s(a)<B/2 and such that Σ_{a∈A} s(a)=mB.
QUESTION: Can A be partitioned into m disjoint sets A_1,A_2,...,A_m such that, for 1<=i<=m, Σ_{a∈A_i} s(a)=B (note that each A_i must therefore contain exactly three elements from A)?
Reference: [Garey and Johnson, 1975]. Transformation from 3DM (see Section 4.2).
Comment: NP-complete in the strong sense.
Reduction Algorithm
The reduction proceeds in two stages as described in Garey & Johnson (1979), Section 4.2.
Stage 1: 3DM -> ABCD-Partition (4-Partition)
Given a 3DM instance with three disjoint sets W, X, Y each of size q and a set M of m triples, where each triple t_k = (w_{i_k}, x_{j_k}, y_{l_k}):
-
Set a base parameter: Let r = 32q (a value polynomial in the input size).
-
Create elements: For each triple t_k = (w_i, x_j, y_l) in M, create four elements with sizes:
- a_k (in set A): s(a_k) = 10r^4 - lr^3 - jr^2 - i*r
- b_k (in set B, corresponding to w_i): s(b_k) = i*r
- c_k (in set C, corresponding to x_j): s(c_k) = j*r^2
- d_k (in set D, corresponding to y_l): s(d_k) = l*r^3
-
Add dummy elements: For each element w_i in W that appears in p_i > 1 triples, add (p_i - 1) dummy elements to set B with size ir. Similarly for X (dummy elements in C with size jr^2) and Y (dummy elements in D with size l*r^3). Each dummy element pairs with one of the extra occurrences.
-
Set target sum: T = 10r^4 (each group of four elements -- one from each of A, B, C, D -- must sum to T).
-
Correctness: A matching M' of size q in the 3DM instance exists iff the ABCD-partition instance has a valid partition. The large polynomial base r ensures that carries in the positional encoding are impossible, making the correspondence exact.
Stage 2: 4-Partition -> 3-Partition
The standard technique converts each group-of-4 constraint into group-of-3 constraints by introducing additional "filler" elements. This is a known polynomial-time reduction (Garey & Johnson, 1979, Section 4.2).
- For each 4-element group, split one element into two parts using auxiliary elements, converting the sum constraint from groups of 4 to groups of 3.
- The resulting 3-PARTITION instance has 3m' elements (where m' depends on the ABCD-partition instance size), bound B', and sizes satisfying B'/4 < s(a) < B'/2.
Key property: All element sizes in the constructed 3-PARTITION instance are bounded by a polynomial in the input size (specifically polynomial in q and m). This is what makes the reduction prove strong NP-completeness -- the result holds even when all numbers are encoded in unary.
Size Overhead
Symbols:
- q = universe size of source 3DM (|W| = |X| = |Y| = q)
- m = number of triples in source 3DM
| Target metric (code name) |
Polynomial (using symbols above) |
num_elements |
O(m) -- linear in the number of triples (4m elements from triples + O(m) dummy elements, then expanded through 4->3 partition step) |
bound |
O(q^4) -- the target sum T = 10*(32q)^4 is polynomial in q |
max_size |
O(q^4) -- individual element sizes are bounded by 10r^4 = 10*(32q)^4 |
Derivation: The ABCD-partition has 4m elements from triples plus at most 3(m - q) dummy elements (since each element of W, X, Y appears in at least one triple and the excess occurrences need dummies). The 4->3 conversion adds a constant factor. All sizes are polynomial in q, establishing strong NP-completeness.
Validation Method
- Closed-loop test: construct a 3DM instance with a known matching, reduce to 3-PARTITION, solve with BruteForce, extract the partition groupings, verify they correspond to a valid matching in the original 3DM instance.
- Verify the strong NP-completeness property: all element sizes in the output should be polynomially bounded in the input size.
- Check that B/4 < s(a) < B/2 holds for all elements (required by the 3-PARTITION definition).
- Test negative instance: a 3DM instance with no perfect matching should produce an infeasible 3-PARTITION instance.
Example
Source instance (3DM):
W = {0, 1}, X = {0, 1}, Y = {0, 1} (q = 2)
Triples (m = 3):
- t_0 = (0, 0, 0)
- t_1 = (1, 1, 1)
- t_2 = (0, 1, 0)
Perfect matching: M' = {t_0, t_1} = {(0,0,0), (1,1,1)} -- each of W, X, Y covered exactly once.
Reduction (Stage 1, ABCD-partition):
r = 32 * 2 = 64, T = 10 * 64^4 = 10 * 16,777,216 = 167,772,160.
For t_0 = (w_0, x_0, y_0): i=0, j=0, l=0
- a_0 = 10r^4 - 0 - 0 - 0 = 167,772,160
- b_0 = 0, c_0 = 0, d_0 = 0
For t_1 = (w_1, x_1, y_1): i=1, j=1, l=1
- a_1 = 10r^4 - 1r^3 - 1r^2 - 1*r = 167,772,160 - 262,144 - 4,096 - 64 = 167,505,856
- b_1 = 64, c_1 = 4,096, d_1 = 262,144
For t_2 = (w_0, x_1, y_0): i=0, j=1, l=0
- a_2 = 10r^4 - 0 - 1*r^2 - 0 = 167,772,160 - 4,096 = 167,768,064
- b_2 = 0, c_2 = 4,096, d_2 = 0
Dummy elements: w_0 appears in t_0 and t_2 (twice), so one dummy b-element with size 0. x_1 appears in t_1 and t_2 (twice), so one dummy c-element with size 4,096. y_0 appears in t_0 and t_2 (twice), so one dummy d-element with size 0.
Groups summing to T = 167,772,160:
- Group for t_0: a_0 + b_0 + c_0 + d_0 = 167,772,160 ✓
- Group for t_1: a_1 + b_1 + c_1 + d_1 = 167,505,856 + 64 + 4,096 + 262,144 = 167,772,160 ✓
The matching {t_0, t_1} corresponds to a valid ABCD-partition.
Note: The subsequent 4->3 partition conversion expands each group further but preserves the polynomial size property.
References
- [Garey and Johnson, 1975]: [
Garey1975] M. R. Garey and D. S. Johnson (1975). "Complexity results for multiprocessor scheduling under resource constraints". SIAM Journal on Computing 4, pp. 397-411.
Source: 3-DIMENSIONAL MATCHING
Target: 3-PARTITION
Motivation: This is the classical reduction proving 3-PARTITION is NP-complete in the strong sense, originally due to Garey & Johnson (1975). It proceeds via an intermediate 4-partition (ABCD-partition) step: 3DM -> 4-partition -> 3-partition. The strong NP-completeness of 3-PARTITION makes it a powerful source for subsequent reductions to scheduling, bin packing, and resource allocation problems.
Reference: Garey & Johnson, Computers and Intractability, SP15, p.224
GJ Source Entry
Reduction Algorithm
The reduction proceeds in two stages as described in Garey & Johnson (1979), Section 4.2.
Stage 1: 3DM -> ABCD-Partition (4-Partition)
Given a 3DM instance with three disjoint sets W, X, Y each of size q and a set M of m triples, where each triple t_k = (w_{i_k}, x_{j_k}, y_{l_k}):
Set a base parameter: Let r = 32q (a value polynomial in the input size).
Create elements: For each triple t_k = (w_i, x_j, y_l) in M, create four elements with sizes:
Add dummy elements: For each element w_i in W that appears in p_i > 1 triples, add (p_i - 1) dummy elements to set B with size ir. Similarly for X (dummy elements in C with size jr^2) and Y (dummy elements in D with size l*r^3). Each dummy element pairs with one of the extra occurrences.
Set target sum: T = 10r^4 (each group of four elements -- one from each of A, B, C, D -- must sum to T).
Correctness: A matching M' of size q in the 3DM instance exists iff the ABCD-partition instance has a valid partition. The large polynomial base r ensures that carries in the positional encoding are impossible, making the correspondence exact.
Stage 2: 4-Partition -> 3-Partition
The standard technique converts each group-of-4 constraint into group-of-3 constraints by introducing additional "filler" elements. This is a known polynomial-time reduction (Garey & Johnson, 1979, Section 4.2).
Key property: All element sizes in the constructed 3-PARTITION instance are bounded by a polynomial in the input size (specifically polynomial in q and m). This is what makes the reduction prove strong NP-completeness -- the result holds even when all numbers are encoded in unary.
Size Overhead
Symbols:
num_elementsboundmax_sizeDerivation: The ABCD-partition has 4m elements from triples plus at most 3(m - q) dummy elements (since each element of W, X, Y appears in at least one triple and the excess occurrences need dummies). The 4->3 conversion adds a constant factor. All sizes are polynomial in q, establishing strong NP-completeness.
Validation Method
Example
Source instance (3DM):
W = {0, 1}, X = {0, 1}, Y = {0, 1} (q = 2)
Triples (m = 3):
Perfect matching: M' = {t_0, t_1} = {(0,0,0), (1,1,1)} -- each of W, X, Y covered exactly once.
Reduction (Stage 1, ABCD-partition):
r = 32 * 2 = 64, T = 10 * 64^4 = 10 * 16,777,216 = 167,772,160.
For t_0 = (w_0, x_0, y_0): i=0, j=0, l=0
For t_1 = (w_1, x_1, y_1): i=1, j=1, l=1
For t_2 = (w_0, x_1, y_0): i=0, j=1, l=0
Dummy elements: w_0 appears in t_0 and t_2 (twice), so one dummy b-element with size 0. x_1 appears in t_1 and t_2 (twice), so one dummy c-element with size 4,096. y_0 appears in t_0 and t_2 (twice), so one dummy d-element with size 0.
Groups summing to T = 167,772,160:
The matching {t_0, t_1} corresponds to a valid ABCD-partition.
Note: The subsequent 4->3 partition conversion expands each group further but preserves the polynomial size property.
References
Garey1975] M. R. Garey and D. S. Johnson (1975). "Complexity results for multiprocessor scheduling under resource constraints". SIAM Journal on Computing 4, pp. 397-411.