[Model] RectilinearPictureCompression

[isPANN]

Motivation

RECTILINEAR PICTURE COMPRESSION (P173) from Garey & Johnson, A4 SR25. A classical NP-complete problem that asks whether a binary matrix can be exactly covered by K or fewer axis-aligned rectangles. The problem arises naturally in image compression (compressing monochromatic bitmap images), DNA array synthesis, integrated circuit manufacturing, and access control list minimization. It connects Boolean satisfiability to geometric covering, serving as a bridge between logic-based and combinatorial optimization problems.

Associated rules:

• R119: 3SAT -> Rectilinear Picture Compression (this model is the target)

Definition

Name: RectilinearPictureCompression
Canonical name: Rectilinear Picture Compression (also: Rectangle Cover, Minimum Rectangle Cover)
Reference: Garey & Johnson, Computers and Intractability, A4 SR25, p.232

Mathematical definition:

INSTANCE: An n x n matrix M of 0's and 1's, and a positive integer K.
QUESTION: Is there a collection of K or fewer rectangles that covers precisely those entries in M that are 1's, i.e., is there a sequence of quadruples (a_i, b_i, c_i, d_i), 1 <= i <= K, where a_i <= b_i, c_i <= d_i, 1 <= i <= K, such that for every pair (i,j), 1 <= i,j <= n, M_{ij} = 1 if and only if there exists a k, 1 <= k <= K, such that a_k <= i <= b_k and c_k <= j <= d_k?

Variables

• Count: The number of candidate rectangles R is O(n^2 * m^2) where n = num_rows, m = num_cols (each rectangle defined by row range [a,b] and column range [c,d], restricted to all-1 rectangles). For the satisfaction formulation, the decision involves selecting which rectangles to include.
• Per-variable domain: binary {0, 1} — whether each candidate rectangle is included in the cover.
• dims(): vec![2; R] where R is the number of maximal all-1 rectangles in the matrix (precomputed from the input).
• evaluate(): Let S = {rectangles i : config[i] = 1}. Return true iff (1) the union of S covers exactly the set of 1-entries in M (no 0-entry covered, every 1-entry covered), and (2) |S| <= bound_k.

Schema (data type)

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

Field	Type	Description
matrix	Vec<Vec<bool>>	The binary matrix M; true = 1, false = 0
bound_k	usize	The positive integer K: maximum number of rectangles allowed

Size fields (getter methods for overhead expressions and declare_variants!):

• num_rows() — returns matrix.len()
• num_cols() — returns matrix[0].len()
• bound_k() — returns bound_k

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed.
• The matrix need not be square in general (GJ specifies n x n, but the problem generalizes to m x n).
• Each rectangle is specified as (a, b, c, d) with a <= b and c <= d, covering rows a..b and columns c..d.
• The cover must be exact: no 0-entry may be covered by any rectangle.

Complexity

• Best known exact algorithm: Brute-force enumeration over all subsets of maximal all-1 rectangles. The number of maximal rectangles in an n x n matrix is at most O(n^2) (each maximal rectangle is determined by its boundary). The exact algorithm tries all combinations of up to K rectangles from the set of maximal rectangles: O(binom(R, K) * n^2) where R is the number of maximal rectangles. In the worst case, R = O(n^2), giving O(n^{2K} * n^2) time. No significantly better exact algorithm is known.
• NP-completeness: NP-complete [Masek, 1978], via transformation from 3SAT.
• References:
  • W. J. Masek (1978). "Some NP-complete set covering problems." Unpublished manuscript, MIT.
  • D. L. Applegate, G. Calinescu, D. S. Johnson, H. Karloff, K. Ligett, J. Wang (2007). "Compressing rectilinear pictures and minimizing access control lists." SODA 2007.

Extra Remark

Full book text:

INSTANCE: An n x n matrix M of 0's and 1's, and a positive integer K.
QUESTION: Is there a collection of K or fewer rectangles that covers precisely those entries in M that are 1's, i.e., is there a sequence of quadruples (ai,bi,ci,di), 1 <= i <= K, where ai <= bi, ci <= di, 1 <= i <= K, such that for every pair (i,j), 1 <= i,j <= n, Mij = 1 if and only if there exists a k, 1 <= k <= K, such that ak <= i <= bk and ck <= j <= dk?
Reference: [Masek, 1978]. Transformation from 3SAT.

Connection to Set Cover: Rectilinear Picture Compression can be viewed as a special case of Set Cover where the universe is the set of 1-entries in M, and the collection consists of all possible axis-aligned rectangles of 1-entries. The constraint that no 0-entry is covered restricts the allowed rectangles to maximal all-1 sub-rectangles.

How to solve

• It can be solved by (existing) bruteforce -- enumerate subsets of maximal all-1 rectangles, check each subset of size <= K for exact coverage.
• It can be solved by reducing to integer programming -- binary variable for each maximal rectangle; constraint that every 1-entry is covered by at least one rectangle; constraint that no 0-entry is covered; objective/constraint that total rectangles <= K.
• Other: Can be formulated as a weighted set cover problem. Practical heuristics based on greedy rectangle selection and local search are effective for moderate instances.

Example Instance

Instance 1 (has solution):
Matrix M (6 x 6):

1 1 1 0 0 0
1 1 1 0 0 0
0 0 1 1 1 0
0 0 1 1 1 0
0 0 0 0 1 1
0 0 0 0 1 1

bound_k = 3

Candidate rectangle cover:

• R1 = (1, 2, 1, 3): rows 1-2, cols 1-3 (covers the top-left 2x3 block of 1's)
• R2 = (3, 4, 3, 5): rows 3-4, cols 3-5 (covers the middle 2x3 block of 1's)
• R3 = (5, 6, 5, 6): rows 5-6, cols 5-6 (covers the bottom-right 2x2 block of 1's)

Verification:

• R1 covers: (1,1),(1,2),(1,3),(2,1),(2,2),(2,3) -- all are 1's in M
• R2 covers: (3,3),(3,4),(3,5),(4,3),(4,4),(4,5) -- all are 1's in M
• R3 covers: (5,5),(5,6),(6,5),(6,6) -- all are 1's in M
• Union of covered entries = all 1-entries in M? Check: M has 1's at rows 1-2 cols 1-3 (6), rows 3-4 cols 3-5 (6), rows 5-6 cols 5-6 (4) = 16 entries. R1+R2+R3 covers 6+6+4 = 16 entries.
• No overlap between rectangles, no 0-entry covered.
• 3 rectangles <= bound_k = 3.

Answer: YES, 3 rectangles suffice.

Instance 2 (no solution with bound_k = 2):
Same matrix M as above, but bound_k = 2.

The three blocks of 1's are disjoint (no rectangle can simultaneously cover 1's from two different blocks without also covering 0-entries). Therefore at least 3 rectangles are needed.

Answer: NO, 2 rectangles are insufficient.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; has planned reduction from 3SAT
Non-trivial	✅ Pass	Distinct geometric covering problem, not isomorphic to any existing model
Correctness	✅ Pass	References verified; NP-completeness and approximation claims confirmed
Well-written	⚠️ Warn	Minor issues: redundant schema fields, approximation claim needs clarification

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The problem RectilinearPictureCompression does not exist in the current codebase. It is a classical NP-complete problem from Garey & Johnson (A4 SR25). The issue mentions a planned reduction R119: 3SAT -> RectilinearPictureCompression, which would connect it to the existing reduction graph via KSatisfiability. The motivation is concrete and well-justified, citing applications in image compression, DNA array synthesis, IC manufacturing, and access control lists.

Non-trivial

This is a genuinely distinct problem. It deals with covering 1-entries of a binary matrix with axis-aligned rectangles — a geometric covering constraint fundamentally different from all existing models. While the issue notes a connection to Set Cover, the geometric structure (rectangles must be axis-aligned, no 0-entry may be covered) makes it a distinct problem with its own complexity characteristics. No existing model is isomorphic.

Correctness

Both cited references were verified:

• [Masek, 1978] — "Some NP-complete set covering problems", unpublished manuscript, MIT. Confirmed as a well-known reference in the literature; the NP-completeness of rectilinear picture compression via this work is widely cited (see Discussions of NP-Complete Problems, Applegate et al. 2007).

• [Applegate et al., 2007] — "Compressing rectilinear pictures and minimizing access control lists", SODA 2007. Confirmed at ACM DL and Semantic Scholar. Authors confirmed: Applegate, Calinescu, Johnson, Karloff, Ligett, Wang.

The NP-completeness via transformation from 3SAT (as stated in GJ) is consistent with the literature.

The brute-force complexity bound is reasonable for a satisfaction problem. No concrete declare_variants! complexity string is provided, but the brute-force analysis is adequate for a satisfaction problem where the search space is well-defined.

Well-written

The issue is well-structured overall with all required sections present and substantive. Minor warnings:

1. Redundant schema fields: rows and cols are explicitly marked as redundant with matrix.len() and matrix[0].len(). Consider removing them and providing getter methods instead to avoid data inconsistency.

2. Approximation claim needs clarification: The issue states "O(sqrt(log k))" approximation from Applegate et al. 2007, but the Applegate et al. paper actually addresses a slightly different formulation (Rectangle Rule Lists with overwriting semantics, not exact covering). The approximation result for the exact covering version may differ. This is a minor concern since it's in the Complexity section rather than the core definition.

3. Variable encoding is well-defined: Unlike some other model issues, this one clearly maps to binary variables over candidate rectangles, which is implementable with dims() returning vec![2; num_candidate_rectangles] and evaluate() checking exact coverage.

4. Example is excellent: Two instances (one satisfiable, one not) with full worked verification. Non-trivial 6x6 matrix with clear geometric structure.

Recommendations

• Remove the redundant rows/cols fields and provide num_rows() and num_cols() getter methods instead.
• Clarify the approximation result attribution or note the distinction between exact-cover and overwriting formulations.
• Consider adding num_ones() as a size getter for overhead expressions.

[isPANN]

Fix-issue changelog

• Removed redundant rows and cols fields from schema (derivable from matrix)
• Renamed budget to bound_k for consistency
• Added size field getters: num_rows(), num_cols(), bound_k()
• Removed unverified approximation claim (Applegate et al. 2007 addresses rectangle rule lists with overwriting semantics, not the exact-cover formulation)

Applied by /fix-issue.