[Model] SparseMatrixCompression

[isPANN]

Motivation

SPARSE MATRIX COMPRESSION (P161) from Garey & Johnson, A4 SR13. A classical NP-complete problem arising in the compact storage of sparse matrices. The idea is to overlay (superimpose) the rows of a binary matrix into a one-dimensional storage vector by assigning each row a shift offset, such that non-zero entries from different rows do not collide. This technique is used in practice for storing sparse DFA transition tables and parser tables (Ziegler's method). The problem asks whether the total storage vector length can be bounded by n + K, where n is the number of columns and K is the maximum shift range. Even, Lichtenstein, and Shiloach (1977) proved NP-completeness via reduction from Graph 3-Colorability, and the problem remains NP-complete even for fixed K = 3.

Associated rules:

• R107: Graph 3-Colorability -> Sparse Matrix Compression (this model is the target)

Definition

Name: SparseMatrixCompression
Canonical name: SPARSE MATRIX COMPRESSION
Reference: Garey & Johnson, Computers and Intractability, A4 SR13, p.229

Mathematical definition:

INSTANCE: An m x n matrix A with entries a_{ij} in {0,1}, 1 <= i <= m, 1 <= j <= n, and a positive integer K <= mn.
QUESTION: Is there a sequence (b_1, b_2, ..., b_{n+K}) of integers b_i, each satisfying 0 <= b_i <= m, and a function s: {1,2,...,m} -> {1,2,...,K} such that, for 1 <= i <= m and 1 <= j <= n, the entry a_{ij} = 1 if and only if b_{s(i)+j-1} = i?

Variables

• Count: m + (n + K) variables total. The shift function s assigns each of the m rows a shift value in {1,...,K} (m variables with domain K). The storage vector b has n + K entries (n + K variables with domain {0,...,m}).
• Per-variable domain: s(i) in {1, 2, ..., K} for each row i; b_j in {0, 1, ..., m} for each storage position j.
• Meaning: s(i) is the offset at which row i is placed in the storage vector. b_j identifies which row (if any) "owns" storage position j. The constraint b_{s(i)+j-1} = i for a_{ij}=1 means each non-zero entry of row i appears at the correct offset position in the storage vector, and no two rows' non-zero entries collide at the same position.

Schema (data type)

Type name: SparseMatrixCompression
Variants: none (no graph or weight parameters)

Field	Type	Description
matrix	Vec<Vec<bool>>	The m x n binary matrix A
num_rows	usize	Number of rows m
num_cols	usize	Number of columns n
bound_k	usize	Maximum shift range K (storage vector length = n + K)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed.
• The storage vector length is n + K (fixed given the instance).
• Alternative encoding: store the matrix in CSR (compressed sparse row) format for efficiency.

Complexity

• Best known exact algorithm: Brute-force: enumerate all K^m possible shift assignments s and check validity. For each assignment, construct the storage vector in O(m * n) and verify no conflicts. Total: O(K^m * m * n). For fixed K=3, this is O(3^m * m * n).
• Complexity string: "(bound_k ^ num_rows) * num_rows * num_cols"
• Approximation: Ziegler's greedy heuristic (place rows one by one, choosing the smallest valid shift) is widely used in practice. Jugé et al. (2026) showed the greedy algorithm has approximation ratio Theta(sqrt(m)) where m is the optimal solution value (Theorem 3.1).
• NP-completeness: NP-complete [Even, Lichtenstein, and Shiloach, 1977], via transformation from Graph 3-Colorability. Remains NP-complete for fixed K = 3.
• References:
  • S. Even, D. I. Lichtenstein, and Y. Shiloach (1977). "Remarks on Ziegler's method for matrix compression." Unpublished manuscript.
  • V. Jugé, D. Köppl, V. Limouzy, A. Marino, J. Olbrich, G. Punzi, and T. Uno (2026). "Revisiting the Sparse Matrix Compression Problem." arXiv:2602.15314.

Extra Remark

Full book text:

INSTANCE: An m x n matrix A with entries aij in {0,1}, 1 <= i <= m, 1 <= j <= n, and a positive integer K <= mn.
QUESTION: Is there a sequence (b1,b2,...,bn+K) of integers bi, each satisfying 0 <= bi <= m, and a function s: {1,2,...,m} -> {1,2,...,K} such that, for 1 <= i <= m and 1 <= j <= n, the entry aij = 1 if and only if bs(i)+j-1 = i?
Reference: [Even, Lichtenstein, and Shiloach, 1977]. Transformation from GRAPH 3-COLORABILITY.
Comment: Remains NP-complete for fixed K = 3.

Practical context: Sparse matrix compression via row overlaying (Ziegler's method) is used to store DFA transition tables compactly. The rows of the transition matrix are overlaid into a single vector, with each row shifted by some offset. Aho, Sethi, and Ullman (the "Dragon Book") recommend this technique for lexer and parser table compression. The NP-completeness result means that finding the optimal compression is intractable, justifying the use of greedy heuristics.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all K^m shift assignments and check for valid overlay.
• It can be solved by reducing to integer programming -- encode shift assignments as integer variables s_i in {1,...,K}, storage vector as integer variables b_j in {0,...,m}, add constraints b_{s_i + j - 1} = i for each a_{ij} = 1 (linearize using big-M or indicator constraints).
• Other: Greedy heuristic (Ziegler's method): process rows in decreasing order of density, assign the smallest shift that avoids conflicts. Also reducible to graph coloring: construct a conflict graph where rows are vertices, edges connect rows that would conflict at some shift difference, and K-color this graph.

Example Instance

Instance (4x4 matrix, K=2):

Matrix A (4 x 4):

Row	c1	c2	c3	c4
r1	1	0	0	1
r2	0	1	0	0
r3	0	0	1	0
r4	1	0	0	0

K = 2, so the storage vector has length n + K = 4 + 2 = 6.

Each row's non-zero column set: r1 = {c1, c4}, r2 = {c2}, r3 = {c3}, r4 = {c1}.

Shift assignment: s(r1) = 2, s(r2) = 2, s(r3) = 2, s(r4) = 1.

Verification: For each row i, the "shifted support" is the set of storage positions {s(i) + j - 1 : a_{ij} = 1}:

• r1 (s=2): positions {2+1-1, 2+4-1} = {2, 5}
• r2 (s=2): positions {2+2-1} = {3}
• r3 (s=2): positions {2+3-1} = {4}
• r4 (s=1): positions {1+1-1} = {1}

All shifted supports are pairwise disjoint: {1}, {2, 5}, {3}, {4}. No conflicts.

Storage vector: b = (b_1, b_2, b_3, b_4, b_5, b_6) = (4, 1, 2, 3, 1, 0).

Biconditional check (a_{ij} = 1 iff b_{s(i)+j-1} = i):

• a_{1,1}=1: b_{2} = 1 = r1 ✓ | a_{1,2}=0: b_{3} = 2 ≠ 1 ✓ | a_{1,3}=0: b_{4} = 3 ≠ 1 ✓ | a_{1,4}=1: b_{5} = 1 = r1 ✓
• a_{2,1}=0: b_{2} = 1 ≠ 2 ✓ | a_{2,2}=1: b_{3} = 2 = r2 ✓ | a_{2,3}=0: b_{4} = 3 ≠ 2 ✓ | a_{2,4}=0: b_{5} = 1 ≠ 2 ✓
• a_{3,1}=0: b_{2} = 1 ≠ 3 ✓ | a_{3,2}=0: b_{3} = 2 ≠ 3 ✓ | a_{3,3}=1: b_{4} = 3 = r3 ✓ | a_{3,4}=0: b_{5} = 1 ≠ 3 ✓
• a_{4,1}=1: b_{1} = 4 = r4 ✓ | a_{4,2}=0: b_{2} = 1 ≠ 4 ✓ | a_{4,3}=0: b_{3} = 2 ≠ 4 ✓ | a_{4,4}=0: b_{4} = 3 ≠ 4 ✓

All 16 entries satisfy the biconditional. Answer: YES.

Uniqueness: This is the only valid shift assignment out of all 2^4 = 16 possible assignments. For example, s = (1, 1, 1, 1) fails because r1 and r4 both map to position 1 (b_1 would need to be both 1 and 4). The 15 failing assignments provide strong test coverage for correctness.

Expected Outcome

This is a satisfaction problem. The instance above has exactly one satisfying assignment:

• Satisfying: s = (2, 2, 2, 1), with storage vector b = (4, 1, 2, 3, 1, 0).
• Non-satisfying examples: s = (1, 1, 1, 1) fails (r1 and r4 collide at position 1); s = (1, 2, 2, 2) fails (r1 and r4 collide at position 1 via different columns); s = (2, 2, 2, 2) fails (r1 and r4 collide at position 2).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem with practical motivation (DFA table compression) and an associated reduction rule
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems — row overlay with shift offsets
Correctness	✅ Pass	Both references verified; complexity claims are sound
Well-written	❌ Fail	Example section contains multiple failed construction attempts with no clean non-trivial worked example

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

SparseMatrixCompression does not exist in the codebase. The problem has a concrete practical motivation (compact storage of sparse DFA transition tables, parser tables), is a recognized problem from Garey & Johnson (SR13), and has an associated reduction rule (R107: Graph 3-Colorability -> Sparse Matrix Compression). The connection to graph coloring also makes it a natural node in the reduction graph. Pass.

Non-trivial

The problem is genuinely distinct from all existing problems in the codebase. The feasibility constraint involves overlaying matrix rows into a 1D storage vector via shift offsets, with a non-collision requirement and a biconditional (if and only if) condition on the storage vector entries. This is structurally different from SAT, ILP, graph problems, and set problems. The variable domains are also non-binary (shift values in {1,...,K}, storage entries in {0,...,m}). Pass.

Correctness

• Even, Lichtenstein, and Shiloach (1977): Confirmed as a real (unpublished) manuscript cited widely in the sparse matrix compression literature. The NP-completeness claim via reduction from Graph 3-Colorability is consistent with multiple secondary sources.
• Juge, Koppl, Limouzy, Marino, Olbrich, Punzi, Uno (2026): Confirmed on arxiv (2602.15314), submitted Feb 2026. The approximation ratio claim of Theta(sqrt(n+K)) for the greedy algorithm matches the paper's abstract.
• Complexity bound: The O(K^m * m * n) brute-force bound is correct for enumeration of all shift assignments.
• NP-completeness for fixed K=3: Consistent with the Garey & Johnson comment.

Well-written

Strengths:

• Mathematical definition is precise and faithful to Garey & Johnson
• Variables section correctly identifies the two variable types (shifts and storage vector entries)
• Schema is reasonable
• Solver methods are well-identified, including the connection to graph coloring

Failures:

• Example section is severely broken: The text contains at least 5 failed attempts at constructing a valid example, with visible "Conflict!", "Revised shift:", and "Wait:" corrections left in the text. The first "Instance 1" fails, gets revised, revised again, revised again, then abandoned. The "Instance (clean, K=2)" also fails. The only successful example is a trivial identity matrix with K=1 that the author acknowledges is trivial. The section ends with "see the reduction example in R107" -- but R107 is a separate issue that may not exist yet.
• No working non-trivial example: A model issue must include at least one non-trivial, fully verified example with known solution. This is missing.
• No declare_variants! complexity string: The Complexity section does not propose a concrete complexity expression for implementation.

Recommendations

• Construct a clean small example (e.g., a 4x3 matrix with K=2) and verify it by hand before including. Remove all failed attempts.
• Since the problem reduces from graph coloring, a good example could start from a known 3-colorable graph, apply the R107 reduction, and present the resulting matrix instance.
• Propose a concrete complexity string (e.g., "bound_k ^ num_rows * num_rows * num_cols" or reference SAT solver bounds via the coloring connection).

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem with practical motivation and associated reduction rule R107
Non-trivial	✅ Pass	Distinct feasibility constraints — row overlay with shift offsets and biconditional storage
Correctness	⚠️ Warn	Approximation ratio misquoted from Jugé et al. (2026); minor author name spelling
Well-written	❌ Fail	Example section contains multiple failed attempts; no clean non-trivial worked example

Overall: 2 passed, 1 warning, 1 failed

Previously (2026-03-12): 3 passed, 0 warnings, 1 failed → Now: 2 passed, 1 warning, 1 failed (correctness downgraded to warning after closer reading of Jugé et al.)

---

Usefulness

SparseMatrixCompression does not exist in the codebase (pred show SparseMatrixCompression returns "Unknown problem"). The problem has concrete practical motivation (compact storage of DFA transition tables, parser tables via Ziegler's method), is a recognized problem from Garey & Johnson (A4 SR13, p.229), and has an associated reduction rule (R107: Graph 3-Colorability → Sparse Matrix Compression). Pass.

Non-trivial

The problem is genuinely distinct from all existing problems. The feasibility constraint involves overlaying matrix rows into a 1D storage vector via shift offsets, with a non-collision requirement and a biconditional (if and only if) condition on the storage vector entries. This is structurally different from all existing problems (SAT, ILP, graph problems, set problems). Variable domains are non-binary (shifts in {1,...,K}, storage entries in {0,...,m}). Pass.

Correctness

References verified:

• Even, Lichtenstein, and Shiloach (1977): Confirmed as a real unpublished manuscript, widely cited in the sparse matrix compression literature. The Jugé et al. (2026) paper cites it as reference [13]. Minor note: the original spelling is "Shiloah", not "Shiloach" as in the issue — this is a common transliteration variant and not a substantive error.

• Jugé et al. (2026), arXiv:2602.15314: Confirmed to exist (submitted Feb 2026, 7 authors match). However, the approximation ratio is misquoted: the issue claims Θ(√(n + K)) but the paper's Theorem 3.1 proves Θ(√(m)) where m is the optimal solution value (optimal array length), not a function of the input dimensions n and K. This is a factual error in the issue.

• Garey & Johnson SR13: Confirmed. The Jugé et al. paper explicitly references "Chapter A4.2, Problem SR13."

• Dragon Book / DFA table compression: Confirmed. Aho, Sethi, and Ullman recommend Ziegler's algorithm for DFA transition table compression (Section 3.9.8).

• NP-completeness for fixed K=3: Confirmed from G&J comment. The Jugé et al. paper actually proves the stronger result that the problem is NP-complete even for maximum shift at most 2.

• Brute-force O(K^m · m · n): Correct reasoning (enumerate K^m assignments, verify each in O(mn)).

Verdict: ⚠️ Warn — the approximation ratio misquote is a factual inaccuracy but does not affect the core definition, NP-completeness, or implementability of the problem. It should be corrected.

Well-written

Strengths:

• Mathematical definition is precise and faithful to Garey & Johnson
• Variables section correctly identifies the two variable types (shifts and storage vector entries)
• Schema is reasonable for the problem structure
• Solver methods are well-identified, including the connection to graph coloring
• Motivation is concrete and well-written

Failures:

1. Example section is severely broken: The text contains at least 5 failed attempts at constructing a valid example, with visible "Conflict!", "Revised shift:", and "Wait:" corrections left in the text. The first "Instance 1" (6×5 matrix) fails, gets revised three times, then is abandoned. The "Instance 1 (revised)" (6×4 matrix) also fails. The "Instance (clean, K=2)" (3×4 matrix) also fails. The only successful example is a trivial 3×3 identity matrix with K=1 that the author acknowledges is trivial. The section ends with "see the reduction example in R107" — but R107 is a separate issue that may not exist yet.
2. No working non-trivial example: A model issue must include at least one non-trivial, fully verified example with expected outcome. The trivial identity matrix example does not meet the round-trip testability requirement (it would pass even with a buggy implementation).
3. Missing concrete complexity expression: The Complexity section does not propose a declare_variants! complexity string for implementation (e.g., "bound_k ^ num_rows * num_rows * num_cols").

Recommendations

• Fix the approximation ratio: Change "Theta(sqrt(n + K))" to "Theta(sqrt(m))" where m is the optimal solution value, per Theorem 3.1 of Jugé et al. (2026).
• Construct a clean example: Remove all failed attempts. A good approach: start from a known 3-colorable graph, mentally apply the R107 reduction to produce a matrix instance, and verify the shift assignment by hand. Alternatively, construct a small matrix (e.g., 4×4 with ~6 non-zero entries) where K=2 suffices, and verify step by step.
• Add a concrete complexity string: e.g., "bound_k ^ num_rows * num_rows * num_cols" for brute-force enumeration.
• Fix author name spelling: "Shiloach" → "Shiloah" (minor, common transliteration variant).

[isPANN]

Fix-issue changelog

• Fixed approximation ratio: "Theta(sqrt(n + K))" → "Theta(sqrt(m)) where m is the optimal solution value" per Jugé et al. (2026) Theorem 3.1
• Added concrete complexity string: "(bound_k ^ num_rows) * num_rows * num_cols"
• Replaced broken example section (5+ failed construction attempts) with a single clean, hand-verified 4×4 matrix example (K=2, unique valid shift s=(2,2,2,1), full biconditional check for all 16 entries)
• Added Expected Outcome section with satisfying assignment and 3 non-satisfying examples

Applied by /fix-issue.