[Rule] X3C to MinimumWeightSolutionToLinearEquations

[isPANN]

Source: X3C
Target: Minimum Weight Solution to Linear Equations
Motivation: This is Garey and Johnson's original reduction proving NP-completeness (in the strong sense) of MINIMUM WEIGHT SOLUTION TO LINEAR EQUATIONS. The reduction encodes the set membership structure of X3C as a linear system where each set becomes a column (its element-incidence vector) and the right-hand side is the all-ones vector. An exact cover of q sets corresponds to a solution vector with exactly q = |U|/3 nonzero entries. The construction is natural and demonstrates the deep connection between combinatorial covering and sparse linear algebra.

Reference: Garey & Johnson, Computers and Intractability, Appendix A6, p.246

GJ Source Entry

[MP5] MINIMUM WEIGHT SOLUTION TO LINEAR EQUATIONS
INSTANCE: Finite set X of pairs (x-bar, b), where x-bar is an m-tuple of integers and b is an integer, and a positive integer K <= m.
QUESTION: Is there an m-tuple y-bar with rational entries such that y-bar has at most K non-zero entries and such that x-bar·y-bar = b for all (x-bar, b) E X?
Reference: [Garey and Johnson, ——]. Transformation from X3C.
Comment: NP-complete in the strong sense. Solvable in polynomial time if K = m.

Reduction Algorithm

Summary:

Given an X3C instance: universe U = {u_1, ..., u_{3q}} and collection C = {C_1, ..., C_n} where each C_j ⊆ U with |C_j| = 3. Question: is there a sub-collection of exactly q sets that partitions U?

Construct a MINIMUM WEIGHT SOLUTION TO LINEAR EQUATIONS instance:

1. Variables: m = n (one variable y_j per set C_j in the collection).

2. Incidence matrix: Construct a 3q x n matrix A where:

   • A_{i,j} = 1 if element u_i ∈ C_j
   • A_{i,j} = 0 otherwise

   Each column j is the characteristic/incidence vector of set C_j.

3. Right-hand side: b = (1, 1, ..., 1)^T ∈ Z^{3q} (the all-ones vector of length 3q). Each element must be covered exactly once.

4. Bound: K = q = |U|/3. The exact cover uses exactly q sets.

5. Equation set X: The set X consists of 3q pairs (row_i(A), 1) for i = 1, ..., 3q, where row_i(A) is the i-th row of A (an n-tuple).

Correctness:

• (forward) If {C_{j_1}, ..., C_{j_q}} is an exact cover, set y_{j_k} = 1 for k = 1,...,q and y_j = 0 otherwise. Then Ay = b (each element covered exactly once) and y has exactly q nonzero entries.
• (backward) If y with at most K = q nonzero rational entries satisfies Ay = b, then the nonzero entries must correspond to sets whose union covers all 3q elements. Since each column has exactly 3 ones and b is all-ones, the nonzero y_j values must all equal 1 (no fractional cover can do better in terms of sparsity while satisfying the 0/1 right-hand side with 0/1 coefficient matrix). The at most q sets with nonzero y_j each cover 3 elements and together cover all 3q elements exactly once, forming an exact cover.

Size Overhead

Symbols:

• n = |C| = number of sets (num_sets of source X3C instance)
• 3q = |U| = number of elements (universe_size)

Target metric (code name)	Polynomial (using symbols above)
num_variables (m)	num_sets (= n)
num_equations (rows of A)	universe_size (= 3q)
bound (K)	universe_size / 3 (= q)

Derivation: One variable per set (n columns). One equation per universe element (3q rows). The incidence matrix is 3q x n with exactly 3 ones per column. K = q = 3q/3. Construction is O(3q * n) time.

Validation Method

• Closed-loop test: construct an X3C instance, reduce to MinimumWeightSolutionToLinearEquations, solve by enumerating all size-K subsets of columns and checking linear system feasibility, verify the result matches the X3C answer.
• Correctness check: for a YES instance, verify the solution vector y has at most K nonzero entries and Ay = b, and that the nonzero entries correspond to a valid exact cover.
• Edge cases: test with no solution (overlapping sets); test with q = 1 (single set = universe); test with redundant sets (n > q, multiple possible covers).

Example

Source instance (X3C):
Universe U = {1, 2, 3, 4, 5, 6} (q = 2, so 3q = 6).
Collection C = {C_1, C_2, C_3, C_4} where:

• C_1 = {1, 2, 3}
• C_2 = {4, 5, 6}
• C_3 = {1, 4, 5}
• C_4 = {2, 3, 6}

Exact covers: {C_1, C_2} or {C_3, C_4}.

Constructed MinimumWeightSolutionToLinearEquations instance:
m = 4 variables, n = 6 equations, K = 2.

Incidence matrix A (6 x 4):

	y_1	y_2	y_3	y_4
u_1	1	0	1	0
u_2	1	0	0	1
u_3	1	0	0	1
u_4	0	1	1	0
u_5	0	1	1	0
u_6	0	1	0	1

b = (1, 1, 1, 1, 1, 1)^T, K = 2.

Verification with y = (1, 1, 0, 0):

• u_1: 11 + 01 + 10 + 00 = 1 -- satisfied
• u_2: 11 + 01 + 00 + 10 = 1 -- satisfied
• u_3: 11 + 01 + 00 + 10 = 1 -- satisfied
• u_4: 01 + 11 + 10 + 00 = 1 -- satisfied
• u_5: 01 + 11 + 10 + 00 = 1 -- satisfied
• u_6: 01 + 11 + 00 + 10 = 1 -- satisfied

Weight of y = 2 (at most K = 2). This corresponds to selecting {C_1, C_2}, which is an exact cover.

Alternative solution y = (0, 0, 1, 1):
Also satisfies Ay = b with weight 2, corresponding to exact cover {C_3, C_4}.

References

• [Garey and Johnson, ----]: (not found in bibliography)