[Model] MinimumMatrixCover

[isPANN]

Motivation

MATRIX COVER (MS13) from Garey & Johnson, A1.2. Given an n×n matrix A of nonneg integers, find a sign assignment f: {1,...,n} → {-1,+1} that minimizes the quadratic form Σ a_ij f(i)f(j). NP-complete in the strong sense, even for positive definite A (Garey and Johnson). The problem is connected to MAX CUT: the adjacency matrix of a graph gives a Matrix Cover instance where minimizing the quadratic form corresponds to maximizing cut edges. Applications in combinatorial optimization, spin glass models, and graph partitioning.

Definition

Name: MinimumMatrixCover
Reference: Garey & Johnson, Computers and Intractability, A1.2 MS13

Mathematical definition:

INSTANCE: n×n matrix A = [a_ij] of nonneg integers.
OBJECTIVE: Find a function f: {1,...,n} → {-1,+1} that minimizes Σ_{1≤i,j≤n} a_ij · f(i) · f(j).

Variables

• Count: n (one per row/column index)
• Per-variable domain: {0, 1} (mapped to {-1,+1} via f(i) = 2x_i - 1)
• Meaning: The sign assignment for each index. The objective is to minimize the quadratic form over these ±1 variables.

Schema (data type)

Type name: MinimumMatrixCover
Variants: none (unique input structure)

Field	Type	Description
matrix	Vec<Vec<i64>>	n×n matrix A of nonneg integers

Complexity

• Best known exact algorithm: O*(2^num_rows) by enumerating all 2^n sign assignments. NP-complete in the strong sense (Garey and Johnson; transformation from MAXIMUM CUT).
• Complexity string: "2^num_rows"

Extra Remark

Full book text:

INSTANCE: n×n matrix A = [a_ij] of nonneg integers, positive integer K.
QUESTION: Does there exist a function f: {1,...,n} → {-1,+1} such that Σ_{1≤i,j≤n} a_ij · f(i) · f(j) ≤ K?

Reference: Transformation from MAXIMUM CUT.
Comment: NP-complete in the strong sense, even for positive definite A.

Note: The original G&J formulation is a decision problem with threshold K (upper bound). We use the equivalent optimization formulation: minimize the quadratic form. Note that for nonneg matrices, maximizing the form is trivial (f = all +1 gives Σ a_ij), but minimizing it is NP-hard — the challenge is finding sign assignments that produce enough negative cross-terms.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n sign assignments and evaluate the quadratic form; return the minimum.)
• It can be solved by reducing to integer programming. (Linearize the quadratic form via McCormick envelopes on binary variables.) See companion issue [Rule] MinimumMatrixCover to ILP #971.
• Other:

Reduction Rule Crossref

• [Rule] MinimumMatrixCover to ILP #971 — [Rule] MinimumMatrixCover to ILP (direct ILP formulation)

Example Instance

Input:
Matrix A (4×4, symmetric, zero diagonal):

0  3  1  0
3  0  0  2
1  0  0  4
0  2  4  0

Sum of all entries: 20.

Optimal sign assignment: f = (-1, +1, +1, -1), value = -20.

Verification: Σ a_ij f(i)f(j) =

• a_{01}·f(0)·f(1) = 3·(-1)·(+1) = -3 (×2 for symmetry)
• a_{02}·f(0)·f(2) = 1·(-1)·(+1) = -1 (×2)
• a_{13}·f(1)·f(3) = 2·(+1)·(-1) = -2 (×2)
• a_{23}·f(2)·f(3) = 4·(+1)·(-1) = -4 (×2)
• Total = 2·(-3-1-2-4) = -20 ✓

The assignment partitions indices into {0,3} (sign -1) and {1,2} (sign +1). All edges cross the partition, so every term contributes negatively.

Suboptimal assignment: f = (+1, +1, -1, -1), value = 8.
Trivial assignment: f = (+1, +1, +1, +1), value = 20 (maximum, all terms positive).

Expected Outcome

Optimal value: Min(-20) — the minimum of the quadratic form is -20. Out of 16 sign assignments, there are 7 distinct values: -20, -8, -4, 0, 4, 8, 20. The optimal is achieved by placing all-connected pairs on opposite sides of the partition.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting MatrixCover to the existing graph
Non-trivial	❌ Fail	Mathematically equivalent to SpinGlass on a complete graph
Correctness	⚠️ Warn	Complexity string uses naive brute-force bound; no specialized algorithm cited
Well-written	❌ Fail	Missing optimization prefix; example too simple for round-trip testing

Overall: 0 passed, 3 failed, 1 warning

---

Usefulness

Fail. The issue does not mention any concrete reduction rule connecting MatrixCover to an existing problem in the reduction graph. The "How to solve" section only checks brute-force, and the body mentions that the problem is "very close to SpinGlass and QUBO in the existing codebase" but does not propose any [Rule] issue linking it. A problem without any planned reduction rule would be an orphan node with no value in the reduction graph.

Non-trivial

Fail. MatrixCover is mathematically equivalent to SpinGlass on a complete graph with no on-site fields (h_i = 0). The MatrixCover objective is:

sum_{i,j=1}^{n} a_{ij} f(i) f(j)

This includes diagonal terms a_{ii} f(i)^2 = a_{ii}, which are constant for all sign assignments. So maximizing this sum is equivalent to maximizing the off-diagonal quadratic form sum_{i<j} (a_{ij} + a_{ji}) f(i) f(j), plus the constant sum_i a_{ii}.

SpinGlass already implements: H(s) = sum_{i<j} J_ij * s_i * s_j + sum_i h_i * s_i over {-1,+1}^n, parameterized by an arbitrary graph. Instantiating SpinGlass on a complete graph with J_ij = -(a_{ij} + a_{ji}) and h_i = 0 gives exactly the negation of the MatrixCover objective (since SpinGlass minimizes and MatrixCover maximizes). The threshold version can be handled by checking whether the SpinGlass minimum is below a derived threshold.

This means MatrixCover is a trivial variant of SpinGlass restricted to complete graphs and zero external fields, not a genuinely new problem. It could alternatively be expressed as a QUBO instance via the standard x_i = (f(i)+1)/2 substitution, which the issue itself acknowledges.

Correctness

Warn. The reference to Garey & Johnson A1.2 MS13 is consistent with the known classification. However:

1. Complexity bound is just brute force. The complexity string "2^num_rows" is the trivial enumeration bound. No specialized exact algorithm is cited. For dense quadratic optimization over {-1,+1}^n, better algorithms may exist (e.g., polynomial-space algorithms for QUBO with improved exponential bases). The issue should cite a concrete best-known algorithm rather than defaulting to brute-force enumeration.

2. Goemans-Williamson claim is imprecise. The issue mentions the 0.878-approximation for MAX CUT as if it applies to this problem, but MatrixCover with a general nonneg matrix is not the same as MAX CUT (which requires a graph Laplacian structure). The GW result applies to MAX CUT specifically, not to arbitrary nonneg quadratic forms.

Well-written

Fail. Several issues:

1. Missing optimization prefix. The definition describes maximizing a quadratic form, so the problem name should use the Maximum prefix (e.g., MaximumMatrixCover or MaximumQuadraticForm). Alternatively, if treated as a decision/feasibility problem with threshold K, the name MatrixCover could work, but then the "How to solve" section and schema need to be consistent with feasibility semantics (Value = Or), not optimization semantics.

2. Decision vs. optimization ambiguity. The issue switches between decision ("Is there a function f such that ... >= K?") and optimization ("maximizes the quadratic form") framing without settling on one. The schema includes a threshold field (decision), but the example discusses "maximum value" (optimization). The codebase SpinGlass uses optimization (Min). The issue needs to pick one framing and be consistent.

3. Example is too simple for round-trip testing. With n=3 there are only 8 configurations and 4 distinct objective values (3, 7, 7, 11). For a meaningful round-trip test, the example should have more variables (at least n=4 or 5) with more diverse feasible/infeasible outcomes to catch implementation bugs. Also, the symmetry f -> -f makes the example degenerate (every assignment and its negation give the same value).

4. Missing Expected Outcome section. The issue should explicitly state the optimal objective value and the optimal solution in a dedicated "Expected Outcome" section.

Recommendations

• Rather than adding MatrixCover as a new model, consider whether the use case is better served by adding a complete-graph variant to SpinGlass, or simply documenting that QUBO already covers this.
• If there is a genuine reason to keep MatrixCover separate (e.g., the dense matrix structure enables specialized algorithms not applicable to sparse SpinGlass), that should be articulated in the Motivation section with a concrete reduction rule connecting it to the graph.
• The complexity string should cite the best known exact algorithm for dense unconstrained quadratic binary optimization, not just brute force.

[isPANN]

Converted from decision framing (MatrixCover with threshold K) to optimization framing (MaximumMatrixCover — maximize quadratic form). Removed Useless, Trivial, and PoorWritten labels. Companion rule issue to follow: MaxCut → MaximumMatrixCover (G&J R332).