[Rule] MaxCut to MinimumMatrixCover

[isPANN]

Source: MaxCut on SimpleGraph with i32 edge weights, restricted to nonnegative integer weights (w(e) >= 0 for every e in E). The MaxCut/SimpleGraph/One (unit-weight) variant is the special case w(e) == 1 and is automatically covered.
Target: MinimumMatrixCover
Motivation: Establishes a direct, witness-preserving reduction MaxCut -> MinimumMatrixCover. The construction takes the symmetric weighted adjacency matrix of G as the target matrix A, exploiting the well-known identity
sum_{i,j} a_{ij} f(i) f(j) = 2 W - 4 * cut(S), where S = { i : f(i) = +1 } and W = sum_{e in E} w(e). Maximizing the cut is therefore equivalent to minimizing the quadratic form, which is exactly what MinimumMatrixCover solves. This is the canonical NP-hardness witness for MinimumMatrixCover (Garey & Johnson, MS13).
Reference: Garey & Johnson, Computers and Intractability (1979), Appendix A1.2, MS13 — "Transformation from MAXIMUM CUT."

Source and target framing

• Source variant. MaxCut/SimpleGraph/i32 with the precondition w(e) >= 0 for all edges. (Unit-weight MaxCut/SimpleGraph/One is a strict special case and is covered without preprocessing.)
  • Value = Max<i32::Sum> (witness-capable).
  • The reduction is witness-preserving: an optimal sign assignment f* for the target maps back to an optimal cut S* = { i : f*(i) = +1 } for the source.
• Target. MinimumMatrixCover with Value = Min<i64>. Instance is an n x n nonnegative integer matrix A (Vec<Vec<i64>>).
• Precondition rationale. MinimumMatrixCover requires nonnegative integer entries (see src/models/algebraic/minimum_matrix_cover.rs). The direct construction a_{ij} = w({i,j}) preserves nonnegativity iff source weights are nonnegative. Negative-weight MaxCut instances are out of scope for this rule and must use a different reduction (e.g., a preprocessing rule that shifts weights and rewrites the objective, registered separately).

GJ Source Entry

[MS13] MATRIX COVER
INSTANCE: n x n matrix A = [a_{ij}] of nonnegative integers.
QUESTION (decision form): Does there exist f : {1,...,n} -> {-1, +1} such that sum_{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. In this codebase the optimization form MinimumMatrixCover is used directly, with Value = Min<i64> (no K parameter).

Reduction Algorithm

Construction (the only construction used by this rule).

Given a MaxCut instance (G, w) with G = (V, E), |V| = n, and nonnegative integer weights w : E -> Z_{>= 0}:

1. Build the n x n adjacency matrix A with i64 entries:

   • a_{ij} = w({i, j}) if {i, j} in E,
   • a_{ij} = 0 otherwise,
   • a_{ii} = 0 for all i.

   A is symmetric, zero-diagonal, and nonnegative — a valid MinimumMatrixCover instance.

2. Forward map (witness). Given a MaxCut cut S subseteq V, set f(i) = +1 if i in S, else f(i) = -1.

3. Backward map (witness extraction). Given an optimal sign assignment f* from MinimumMatrixCover, return S* = { i in V : f*(i) = +1 }. The complementary set V \ S* is also optimal (the symmetry f -> -f leaves the quadratic form invariant).

Key identity. For any f in {-1, +1}^n and the corresponding S = { i : f(i) = +1 }:

sum_{i, j} a_{ij} f(i) f(j) = 2 W - 4 * cut(S),

where W = sum_{e in E} w(e) is the total edge weight and cut(S) = sum_{ {i, j} in E, |S cap {i, j}| = 1 } w({i, j}).

Proof of identity. Each edge {i, j} in E contributes to the double sum sum_{i, j} a_{ij} f(i) f(j) twice (once as (i, j), once as (j, i)):

• If {i, j} is not cut by S, both endpoints share a sign, so f(i) f(j) = +1 and the edge contributes +2 w({i, j}).
• If {i, j} is cut, the endpoints disagree, so f(i) f(j) = -1 and the edge contributes -2 w({i, j}).

Summing: sum_{i, j} a_{ij} f(i) f(j) = 2 (W - cut(S)) - 2 cut(S) = 2 W - 4 cut(S). QED.

Objective equivalence. Because 2 W is a constant depending only on the source instance,

min_f sum_{i, j} a_{ij} f(i) f(j) = 2 W - 4 * max_S cut(S),

so

MaxCut(G, w) = (2 W - MinimumMatrixCover(A)) / 4.

Witness correctness. A sign assignment f* minimizes the quadratic form iff S* = { i : f*(i) = +1 } (equivalently, its complement) maximizes the cut. The MinimumMatrixCover brute-force solver returns one such f* directly, and the backward map yields a maximum cut.

Time complexity of the reduction itself. O(n^2) to materialize A.

Size Overhead

Symbols:

• num_vertices — n = |V| of the source graph.

Target metric (code name)	Polynomial (using source symbols)	Big-O
num_rows	num_vertices	O(num_vertices)

MinimumMatrixCover's only size field is num_rows = n. The matrix has n^2 entries but that is a derived quantity, not a size field.

Validation Method

• Closed-loop test (mandatory). For several small instances (G, w):
  1. Construct the source MaxCut/SimpleGraph/i32 with nonneg integer weights.
  2. Apply this reduction to obtain MinimumMatrixCover(A).
  3. Solve the target via BruteForce to obtain min_qf and a witness f*.
  4. Verify MaxCut(G, w) = (2 W - min_qf) / 4 by also solving the source via BruteForce.
  5. Verify witness extraction: S* = { i : f*(i) = +1 } is an optimal cut in G (equal weight to the source-side optimum).
• Unit-weight cases. K_3 (max cut = 2), K_{2,2} (max cut = 4), C_4 (max cut = 4 — see the worked example).
• Weighted nonneg cases. Path graph P_3 with weights (2, 3) — max cut = 5, single optimal partition mod symmetry.
• Edge cases. Empty graph (matrix = 0, max cut = 0); single isolated edge with isolated vertices; disconnected union of two triangles.
• Identity check. For at least one small n, iterate over all 2^n sign assignments and confirm sum_{i, j} a_{ij} f(i) f(j) = 2 W - 4 cut(S) for every f.
• Precondition test. Construct a MaxCut/SimpleGraph/i32 instance with a negative edge weight and assert that reduce_to panics or returns an error (the rule does not handle this variant).

Example

Source instance (MaxCut/SimpleGraph/i32, nonneg weights).

Graph G = (V, E) with V = {0, 1, 2, 3}, edges E = { {0,1}, {1,2}, {2,3}, {0,3} } (the 4-cycle C_4), all weights w({i, j}) = 1. Then W = 4. Maximum cut: S* = {0, 2} (or symmetrically {1, 3}), cutting all 4 edges, so MaxCut(G, w) = 4.

Constructed target instance (MinimumMatrixCover).

A is the weighted adjacency matrix of G:

       j=0 j=1 j=2 j=3
i=0:    0   1   0   1
i=1:    1   0   1   0
i=2:    0   1   0   1
i=3:    1   0   1   0

All entries are nonnegative integers, the diagonal is zero, and A is symmetric — a valid MinimumMatrixCover instance.

Solving the target. Enumerate all 16 sign assignments and compute qf(f) = sum_{i, j} a_{ij} f(i) f(j):

f	S = { i : f(i) = +1 }	cut(S)	qf(f) = 2W - 4 cut(S)
(+1, +1, +1, +1)	{0, 1, 2, 3}	0	+8
(+1, -1, +1, -1)	{0, 2}	4	-8
(-1, +1, -1, +1)	{1, 3}	4	-8
(+1, +1, -1, -1)	{0, 1}	2	0

(Other rows omitted; the minimum is -8.)

So MinimumMatrixCover(A) = -8, attained by f* = (+1, -1, +1, -1) (and its negation).

Recovered cut. S* = { i : f*(i) = +1 } = {0, 2}. Check the formula: MaxCut(G, w) = (2 W - min_qf) / 4 = (2 * 4 - (-8)) / 4 = 16 / 4 = 4. Matches. The recovered S* is exactly a maximum cut of G.

Notes / Alternative constructions (informational, not used by this rule)

For completeness, two constructions sometimes appear in the literature; this rule does not use them. They are listed here only to head off confusion:

• Complement-graph construction. Set A to be the weighted adjacency matrix of the complement graph bar{G}. This swaps the roles of cut and non-cut edges in the quadratic form and is irrelevant once we are minimizing (rather than maximizing) directly. Not used.
• Weight-shifting for negative-weight MaxCut. A separate (future) reduction may handle negative weights by adding a constant c >= -min_e w(e) to all entries of A and tracking the resulting additive shift in the objective. This is not part of the present rule, which restricts to nonneg-weight sources.

References

• [Garey and Johnson, 1979]: M. R. Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, p. 226 (MS13).
• [Goemans and Williamson, 1995]: M. X. Goemans and D. P. Williamson (1995). "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming." Journal of the ACM 42(6), pp. 1115-1145. (Background on MaxCut; not used in the NP-hardness reduction itself.)

[isPANN]

Note: Target problem renamed and objective direction corrected

The target problem was renamed from MaximumMatrixCover to MinimumMatrixCover (issue #931). The G&J MS13 formulation asks whether Σ a_ij f(i)f(j) ≤ K (minimize), not ≥ K (maximize). Maximizing is trivial for nonneg matrices (f = all +1 gives Σ a_ij).

The reduction direction and motivation remain correct: MaxCut encodes graph partitioning as minimizing the quadratic form over ±1 variables via the adjacency matrix. Edges crossing the cut contribute negative terms, so minimizing the form corresponds to maximizing the cut.

The GJ Source Entry in this issue's body contains the incorrect direction (≥ K) and should be updated to ≤ K when this rule is implemented.

[isPANN]

Issue Quality Check — Rule (Re-check)

Check	Result	Details
Usefulness	Pass	No existing path MaxCut → MinimumMatrixCover; novel direct reduction
Non-trivial	Pass	Real structural mapping via the identity Σ a_ij f(i)f(j) = 2W − 4·cut(S); not a relabeling
Correctness	Warn	G&J MS13 is a real citation and supports MaxCut → MATRIX COVER, but issue body still carries the old ≥ K direction and is internally inconsistent after the rename (target text says "Matrix Cover", G&J quote is in the wrong direction). The contributor's own follow-up comment already flagged this.
Completeness	Fail (Incomplete)	The natural construction A_ij = w({i,j}) requires nonneg integer edge weights but the algorithm and the target source variant are not restricted. On MaxCut/SimpleGraph/i32 with any negative edge weight the constructed A violates MinimumMatrixCover's nonneg integer matrix instance constraint.
Well-written	Fail (PoorWritten)	The "Reduction Algorithm" section presents a clean construction (A = weighted adjacency, K from 2W − 4·K_cut) and then offers two alternative constructions ("complement approach", "complementary matrix") without picking one. For the renamed optimization target MinimumMatrixCover (no K), the entire threshold/transformation discussion is moot and confusing. The worked example silently switches from the adjacency-matrix construction to the complement-graph construction mid-paragraph.

Overall: 2 pass, 1 warning, 2 fail. Labels: Incomplete, PoorWritten.

---

Usefulness

pred path MaxCut MinimumMatrixCover returns "No reduction path" on main — this would be a novel direct edge. Motivation is concrete: it gives a sign-assignment formulation of MaxCut over a nonneg integer matrix, which is also the canonical NP-hardness witness for MinimumMatrixCover in G&J MS13. Pass.

Non-trivial

The construction is not a relabeling: it builds a new aggregate object (the n×n matrix) whose optima correspond to maximum cuts via the quadratic-form identity. Verified the identity numerically on the issue's own C_4 example:

For every f ∈ {-1,+1}^4, Σ a_ij f(i) f(j) = 2W − 4·cut(S) holds.
e.g. f = (-1,+1,-1,+1): cut = 4, qf = -8, 2W − 4·cut = 8 − 16 = -8 ✓

Pass.

Correctness

References are real:

• Garey & Johnson, Computers and Intractability, A1.2 MS13 — already cited in docs/paper/references.bib. The MS13 entry explicitly cites "Transformation from MAXIMUM CUT", which is the direction proposed here.
• Goemans–Williamson 1995 — real, but this is an approximation paper for MaxCut/MaxSAT, not a source for the NP-hardness reduction. It is fine as a background citation but does not support the reduction proper.

Issues with the issue text (not the math):

• The "GJ Source Entry" still reads Σ a_ij f(i) f(j) ≥ K? This is the maximization version. After issue [Model] MinimumMatrixCover #931 renamed the target to MinimumMatrixCover (minimize Σ ≤ K in the decision form, or just minimize in the codebase's optimization form), this block needs to be updated to ≤ K (or simply replaced by the codebase's optimization formulation). The contributor's own comment on this issue acknowledges this.
• The target line "Target: Matrix Cover" should read "Target: MinimumMatrixCover" (this is the registered name in pred show).
• The math identity Σ a_ij f(i)f(j) = 2W − 4·cut(S) is correct for the symmetric adjacency-matrix construction.

Warn (not Fail): the literature claims are correct and traceable; the prose just needs to be reconciled with the rename.

Completeness

This is the load-bearing check for [Rule] issues. Performed both literature research and codebase corner-case tracing.

Literature (G&J MS13). G&J states MATRIX COVER as: "n×n matrix A = [a_ij] of nonneg integers" with reference "Transformation from MAXIMUM CUT" and comment "NP-complete in the strong sense, even for positive definite A." The reduction in G&J takes the (symmetric, zero-diagonal, nonneg) adjacency matrix of a MaxCut instance directly — i.e., it implicitly assumes a nonneg integer-weighted source MaxCut. The original Karp-style MaxCut is unweighted (every edge has weight 1), which is automatically nonneg integer; G&J's transformation does not state a treatment for negative or fractional edge weights.

Codebase source variants. pred list exposes two MaxCut variants:

• MaxCut/SimpleGraph/One — unit weights (always 1)
• MaxCut/SimpleGraph/i32 — signed integer weights (can be negative)

The issue's algorithm sets a_ij = w({i,j}) if {i,j} ∈ E. This works for MaxCut/SimpleGraph/One (trivially nonneg), but on MaxCut/SimpleGraph/i32 with any negative edge weight the constructed A will have negative entries, which violates MinimumMatrixCover's explicit Vec<Vec<i64>> nonneg integer matrix instance constraint (see src/models/algebraic/minimum_matrix_cover.rs and the G&J MS13 instance definition). The issue body does not state which source variant is targeted and does not declare a nonneg-weight precondition.

Corner cases traced (algorithm-by-hand):

1. Empty graph (n = 3, no edges). A is the 3×3 zero matrix; every sign assignment gives qf = 0, and MaxCut value is 0 for every partition. Min qf = 0 corresponds (vacuously) to any partition. Algorithm OK.
2. Single edge n = 2 (unit weight). A = [[0,1],[1,0]]. qf attains {2, −2, −2, 2} on the four sign assignments. Min qf = −2 attained by f = (+1,−1) and f = (−1,+1); both yield S of size 1, MaxCut = 1. Algorithm OK.
3. Isolated vertices (n = 4, single edge {0,1}, unit weight). Verified by brute force: min qf = −2, attained by 8 sign assignments. Every extracted partition S = {i : f(i) = +1} yields cut = 1 = the maximum cut. Algorithm OK on this corner case.
4. Negative edge weight (the failing case). MaxCut/SimpleGraph/i32 with n = 2, edge (0,1) with weight -1. Naive construction yields A = [[0,-1],[-1,0]], not a valid MinimumMatrixCover instance (Vec<Vec<i64>> of nonneg integers). The algorithm as written does not check this and would produce an invalid target. Algorithm BREAKS.

Verdict: Fail. Either (a) declare the source explicitly as MaxCut/SimpleGraph/One, (b) restrict to MaxCut/SimpleGraph/i32 with a stated w(e) ≥ 0 precondition (and add a preprocessing or domain check), or (c) state how negative weights are handled (e.g., shift all weights by a constant offset and adjust the threshold/objective accordingly — note that a uniform shift changes the optimum by a known additive constant).

The issue body also mentions a "complement approach" / "complementary matrix" that, on inspection, does not fix this problem: the example actually computed in the "Constructed target instance" section uses the complement graph's adjacency matrix (entries {0,2} and {1,3} rather than the original edges {0,1},{1,2},{2,3},{0,3}), but this alternative construction (i) is not what the algorithm formally states and (ii) does not help with negative weights either. The two constructions are conflated, which is also why the Well-written check fails.

Well-written

Specific issues to fix:

1. Target inconsistency. Body says "Target: Matrix Cover"; title says MinimumMatrixCover. Use the registered name MinimumMatrixCover (verified via pred show MinimumMatrixCover).
2. GJ Source Entry has the wrong direction. ≥ K should be ≤ K to match the minimizing G&J form (and the codebase's Min<i64> value type for MinimumMatrixCover). The contributor's follow-up comment already flagged this.
3. Ambiguous algorithm. Step 3 ("Threshold transformation") offers a primary construction and two alternatives ("complement approach", "complementary matrix") without choosing one. Since the target is now an optimization problem with no K, the threshold-juggling discussion can be deleted; pick one construction (the natural A_ij = w({i,j})) and commit to it.
4. Example switches constructions. The example narrative says A_ij = w({i,j}) and shows the right matrix, but then "for Matrix Cover formulation with threshold" silently switches to the complement-graph matrix. Pick one construction and show one consistent example.
5. Source variant not specified. Add the source variant (e.g., MaxCut<SimpleGraph, One> or MaxCut<SimpleGraph, i32> with nonneg weights) and state the precondition on edge weights.
6. Solution extraction wording. "The partition S = {i : f(i) = +1} gives the maximum cut" — confirmed correct by hand-trace; keep this and place it directly under a clean Step-by-step algorithm.
7. Size Overhead table. num_rows = num_vertices is correct; this part is fine.

Recommendations

• Pick the single, clean construction: A_ij = w(i,j) if (i,j) ∈ E else 0; a_ii = 0. Solve MinimumMatrixCover on A. Extract S = {i : f(i) = +1}. Cut weight = (W − qf/2) / 2 for symmetric A (or just: max cut = (2W − min qf)/4 when w is unit/integer; see hand-trace).
• Drop the "complement matrix" alternative and the threshold transformation paragraphs; they were artifacts of the old MaximumMatrixCover, Σ ≥ K framing and are no longer needed.
• For the source variant, the cleanest target is MaxCut<SimpleGraph, One> (always nonneg, matches G&J's unweighted MaxCut directly). If a weighted variant is desired, add MaxCut<SimpleGraph, i32> with an explicit nonneg-weights precondition.
• The example C_4 has multiple suboptimal cuts (cut = 2 is attainable many ways) and the optimal cut = 4 — good round-trip test material. After cleanup, keep this example.

[isPANN]

auto-pipeline: parked on OnHold — A_ij = w({i,j}) produces negative-entry matrix on weighted MaxCut, violating MinimumMatrixCover's non-negative integer constraint. Issue offers two contradictory alternatives without committing. See #925 (comment)