Reduction

Source: ExactCoverBy3Sets (exists in codebase)
Target: MinimumWeightSolutionToLinearEquations (issue #854)
Reference: Garey & Johnson, R156 (A6 MP5)

Construction

Given an X3C instance (universe U = {u_1, ..., u_{3q}}, collection C = {C_1, ..., C_t} of 3-element subsets of U):

Construct a linear system Ax = b where:

• A is a (3q) ×ばつ t incidence matrix: A_{ij} = 1 if u_i ∈ C_j, else 0
• b = (1, 1, ..., 1) (all-ones vector of length 3q)

The X3C instance has an exact cover iff the minimum-weight solution to Ax = b has Hamming weight q. An exact cover selects exactly q sets covering each element once, corresponding to a 0/1 solution with exactly q nonzero entries.

Correctness sketch

Forward: If C' ⊆ C is an exact cover of size q, define x_j = 1 if C_j ∈ C', else 0. Then Ax = b (each element covered exactly once) and the Hamming weight is q.

Backward: If x is a solution with Hamming weight ≤ q, the covering constraint forces each row sum to equal 1. Since each column contributes exactly 3 to the total row sum (3-element subsets), at least q columns must be nonzero (3q/3 = q). So the minimum weight is exactly q and corresponds to an exact cover.

Dependencies

• Source ExactCoverBy3Sets: exists in codebase
• Target MinimumWeightSolutionToLinearEquations: issue [Model] MinimumWeightSolutionToLinearEquations #854