[Model] ConsecutiveOnesMatrixAugmentation

[isPANN]

Motivation

CONSECUTIVE ONES MATRIX AUGMENTATION (P164) from Garey & Johnson, A4 SR16. An NP-complete problem from the domain of storage and retrieval, asking whether a binary matrix can be made to have the consecutive ones property (C1P) by changing at most K zeros to ones. It arises in information retrieval, physical mapping of DNA, and sparse matrix compression. The C1P is testable in polynomial time using PQ-trees, but augmenting a matrix to achieve it is NP-complete.

Associated rules:

• R110: Optimal Linear Arrangement -> Consecutive Ones Matrix Augmentation (as target)

Definition

Name: ConsecutiveOnesMatrixAugmentation
Canonical name: CONSECUTIVE ONES MATRIX AUGMENTATION
Reference: Garey & Johnson, Computers and Intractability, A4 SR16

Mathematical definition:

INSTANCE: An m x n matrix A of 0's and 1's and a positive integer K.
QUESTION: Is there a matrix A', obtained from A by changing K or fewer 0 entries to 1's, such that A' has the consecutive ones property for columns? (That is, there exists a permutation of the columns of A' such that in each row the 1's appear consecutively.)

Variables

• Count: The decision variables are: (1) a column permutation (n! possibilities), and (2) which zero entries to flip to one (at most K of the m*n - nnz(A) zero entries).
• Per-variable domain: For the column permutation: each column maps to a position in {1, ..., n}. For the augmentation: each zero entry is either flipped (1) or not (0).
• Meaning: A satisfying assignment is a set S of zero-entries of A with |S| <= K, and a column permutation pi, such that after flipping S to ones and applying pi, every row has its ones in a contiguous block.

Schema (data type)

Type name: ConsecutiveOnesMatrixAugmentation
Variants: None

Field	Type	Description
matrix	Vec<Vec<bool>>	The m x n binary matrix A (row-major)
bound	i64	The positive integer K (max number of 0->1 flips allowed)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The consecutive ones property (C1P) for columns means there exists a column permutation such that in every row the 1-entries are contiguous.
• The variant asking for the circular ones property (1's wrap around) is also NP-complete per GJ.

Complexity

• Best known exact algorithm: O(n! · m · n) by enumerating all n! column permutations and for each computing the minimum 0→1 flips needed per row in O(m · n) time. For fixed K, the problem may admit FPT algorithms parameterized by K.
• Complexity string: "factorial(num_cols) * num_rows * num_cols"
• NP-completeness: NP-complete [Booth, 1975, Theorem 4.19], [Papadimitriou, 1976a]. Both independently observed that the k-augmented C1P problem is NP-complete, via reduction from Simple Optimal Linear Arrangement. G&J cites [Papadimitriou, 1976a] which is the bandwidth minimization paper; the NP-completeness observation for C1P augmentation appeared in the earlier technical report (TR-173, Princeton, December 1974).
• Related polynomial results: Testing whether a matrix already has the C1P (K=0) is solvable in linear time O(m + n + number of ones) using PQ-trees [Booth and Lueker, 1976].
• Approximation: Negative results are known: a large class of simple augmentation algorithms cannot find a near-optimum solution [Veldhorst, 1985].
• References:
  • K. S. Booth (1975). "PQ Tree Algorithms." Ph.D. thesis, University of California, Berkeley.
  • K. S. Booth and G. S. Lueker (1976). "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms." J. Computer and System Sciences, 13:335-379.
  • C. H. Papadimitriou (1976). "The NP-completeness of the bandwidth minimization problem." Computing, 16:263-270.
  • M. Veldhorst (1985). "Approximation of the consecutive ones matrix augmentation problem." SIAM Journal on Computing, 14(3):709-729.

Extra Remark

Full book text:

INSTANCE: An m x n matrix A of 0's and 1's and a positive integer K.
QUESTION: Is there a matrix A', obtained from A by changing K or fewer 0 entries to 1's, such that A' has the consecutive ones property?
Reference: [Booth, 1975], [Papadimitriou, 1976a]. Transformation from OPTIMAL LINEAR ARRANGEMENT.
Comment: Variant in which we ask instead that A' have the circular ones property is also NP-complete.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all column permutations and for each, count the minimum number of 0->1 flips needed to make each row consecutive; check if total <= K.
• It can be solved by reducing to integer programming -- binary variables for column ordering and augmentation decisions, with C1P constraints linearized.
• Other: PQ-tree based approaches can enumerate valid orderings efficiently when the matrix is close to having C1P; branch-and-bound with C1P feasibility tests.

Example Instance

Instance 1 (YES instance):

This matrix is the vertex-edge incidence matrix of a graph on 4 vertices {0,1,2,3} with 5 edges: {0,1}, {1,2}, {2,3}, {0,3}, {0,2}. Rows correspond to vertices and columns to edges.

Matrix A (4 x 5):

Row 0: [1, 0, 0, 1, 1]   (vertex 0: incident to e01, e03, e02)
Row 1: [1, 1, 0, 0, 0]   (vertex 1: incident to e01, e12)
Row 2: [0, 1, 1, 0, 1]   (vertex 2: incident to e12, e23, e02)
Row 3: [0, 0, 1, 1, 0]   (vertex 3: incident to e23, e03)

K = 2

Column permutation: π = [0, 1, 4, 2, 3] (reorder columns as e01, e12, e02, e23, e03).

After applying π:

Row 0: [1, 0, 1, 0, 1]   — 1's at positions 0, 2, 4 (gaps at 1 and 3)
Row 1: [1, 1, 0, 0, 0]   — 1's at positions 0, 1 (consecutive, no flips needed)
Row 2: [0, 1, 1, 1, 0]   — 1's at positions 1, 2, 3 (consecutive, no flips needed)
Row 3: [0, 0, 0, 1, 1]   — 1's at positions 3, 4 (consecutive, no flips needed)

Only Row 0 needs augmentation: flip A[0][1] = 0→1 and A[0][2] = 0→1 (2 flips).

Augmented matrix A' after permutation π (C1P verified):

Row 0: [1, 1, 1, 1, 1]   — consecutive ✓
Row 1: [1, 1, 0, 0, 0]   — consecutive ✓
Row 2: [0, 1, 1, 1, 0]   — consecutive ✓
Row 3: [0, 0, 0, 1, 1]   — consecutive ✓

Total flips: 2 ≤ K = 2. Answer: YES.

Brute-force verification (120 total permutations): 8 permutations achieve 2 flips (optimal), 32 achieve 3, 40 achieve 4, 32 achieve 5, 8 achieve 6. No permutation achieves 0 or 1 flip, confirming K = 2 is tight.

Instance 2 (NO instance):

Matrix A (4 x 4):

Row 0: [1, 0, 1, 0]
Row 1: [0, 1, 0, 1]
Row 2: [1, 1, 0, 1]
Row 3: [0, 1, 1, 0]

K = 0

Brute-force verification: all 24 column permutations require at least 1 flip to achieve C1P. The best permutations need exactly 1 flip (4 permutations), while others need 2 (8 perms), 3 (8 perms), or 4 (4 perms). Since K = 0 and no permutation achieves C1P with 0 flips, the answer is NO.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem with applications in information retrieval and DNA mapping
Non-trivial	✅ Pass	Distinct from ConsecutiveOnesSubmatrix -- augmentation (0->1 flips) vs column selection
Correctness	❌ Fail	Example Instance 2 (NO instance) is mathematically incorrect -- the matrix actually has C1P
Well-written	⚠️ Warn	Schema uses Vec<Vec> instead of Vec<Vec>; minor notation issues

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

ConsecutiveOnesMatrixAugmentation does not exist in the codebase. The problem is distinct from ConsecutiveOnesSubmatrix (#417) and ConsecutiveOnesMatrixPartition (#418) -- this one asks about flipping zeros to ones to achieve C1P, rather than selecting columns or partitioning rows. It has practical applications in information retrieval and DNA physical mapping, and an associated reduction rule (R110: Optimal Linear Arrangement -> Consecutive Ones Matrix Augmentation). Pass.

Non-trivial

The problem is genuinely distinct from all existing problems. The feasibility constraint combines a column permutation with a bounded number of 0-to-1 entry modifications, requiring that the augmented matrix satisfy the consecutive ones property. This is structurally different from SAT, graph problems, and other matrix problems in the codebase. Pass.

Correctness

• Booth (1975): Confirmed. "PQ Tree Algorithms," Ph.D. Thesis, UC Berkeley.

• Booth and Lueker (1976): Confirmed. "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms," JCSS 13, pp. 335-379.

• Papadimitriou (1976): The cited paper "The NP-completeness of the bandwidth minimization problem," Computing 16:263-270, is confirmed to exist. However, this paper is about bandwidth minimization, not directly about consecutive ones matrix augmentation. The Garey & Johnson entry references "[Papadimitriou, 1976a]" (with the "a" suffix indicating a specific paper among multiple 1976 publications), and the reduction is stated as being from OPTIMAL LINEAR ARRANGEMENT. The connection between bandwidth/linear arrangement and C1P augmentation is plausible but the exact paper may be a different Papadimitriou 1976 publication.

• Hochbaum and Levin (1985): Mentioned in the Complexity section regarding negative approximation results, but not listed in References. Cannot be verified.

• Example Instance 2 is WRONG: The NO instance matrix:

  Row 0: [1, 0, 0, 0, 0, 1]  -- 1's at columns 0 and 5
  Row 1: [0, 1, 0, 0, 1, 0]  -- 1's at columns 1 and 4
  Row 2: [0, 0, 1, 1, 0, 0]  -- 1's at columns 2 and 3
  

  with K=0 is claimed to NOT have C1P. However, the column permutation [0, 5, 1, 4, 2, 3] yields:

  • Row 0: cols 0,5 at positions 0,1 -- consecutive
  • Row 1: cols 1,4 at positions 2,3 -- consecutive
  • Row 2: cols 2,3 at positions 4,5 -- consecutive

  This matrix DOES have the consecutive ones property. The NO instance is incorrect.

Well-written

Strengths:

• Mathematical definition is precise and faithful to Garey & Johnson
• Variables section correctly describes the two-part decision (permutation + augmentation)
• Example Instance 1 (YES instance) is well-constructed and fully verified
• Solver methods are well-identified

Minor issues:

• Schema uses Vec<Vec<u8>> instead of Vec<Vec<bool>> -- inconsistent with other matrix-based models in the codebase which use bool for binary matrices.
• The Hochbaum and Levin (1985) reference is mentioned in the text but not in the References section.
• No declare_variants! complexity string proposed.

Recommendations

• Fix Example Instance 2: construct a genuine NO instance. A simple approach: create a matrix that contains a Tucker obstruction (e.g., the 3x3 identity matrix lacks C1P when augmented with specific additional rows) and set K=0.
• Add the Hochbaum and Levin reference to the References section or remove the claim.
• Consider using Vec<Vec<bool>> for consistency with other models.

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check (2026-03-12): 2 passed, 1 failed (Wrong), 1 warning. Re-checking with --force.

Check	Result	Details
Usefulness	✅ Pass	Novel problem; distinct from ConsecutiveOnesSubmatrix, ConsecutiveBlockMinimization, ConsecutiveOnesMatrixPartition
Non-trivial	✅ Pass	Distinct feasibility constraint: bounded 0→1 flips + column permutation for C1P
Correctness	⚠️ Warn	Booth (1975), Booth & Lueker (1976) confirmed; Papadimitriou (1976a) reference is the bandwidth paper — connection to C1P unclear; complexity expression questionable
Well-written	❌ Fail	Example Instance 2 is mathematically wrong; schema inconsistent with existing consecutive-ones models

Overall: 2 passed, 1 warning, 1 failed

Previously: 2 passed, 1 failed, 1 warning → Now: same pattern, confirming previous findings.

---

Usefulness

• ConsecutiveOnesMatrixAugmentation does not exist in the codebase.
• Distinct from related problems:
  • ConsecutiveOnesSubmatrix ([Model] ConsecutiveOnesSubmatrix #417): select K columns that admit C1P
  • ConsecutiveBlockMinimization: minimize total consecutive blocks
  • ConsecutiveOnesMatrixPartition ([Model] ConsecutiveOnesMatrixPartition #418): partition rows into C1P groups
• Has a planned reduction rule R110 (OptimalLinearArrangement → ConsecutiveOnesMatrixAugmentation), connecting it to the existing graph.
• Concrete motivation: information retrieval, DNA physical mapping, sparse matrix compression.
• Solver methods identified: brute-force, ILP, PQ-tree approaches.

Non-trivial

The problem has a genuinely distinct feasibility constraint from all existing problems. It combines two decisions:

1. A column permutation (ordering)
2. A bounded set of 0→1 entry modifications (augmentation)

...such that the augmented matrix has the consecutive ones property. This differs from ConsecutiveOnesSubmatrix (column selection, not augmentation), ConsecutiveBlockMinimization (no augmentation, minimize blocks), and other matrix problems. Pass.

Correctness

Booth (1975): ✅ Confirmed. "PQ Tree Algorithms," Ph.D. thesis, UC Berkeley. The thesis covers PQ-tree algorithms for the consecutive ones property and related NP-completeness results.

Booth and Lueker (1976): ✅ Confirmed. "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms," JCSS 13:335-379. Linear-time C1P testing as claimed.

Papadimitriou (1976a): ⚠️ The issue cites this as "The NP-completeness of the bandwidth minimization problem" (Computing 16:263-270). This paper exists and is confirmed, but its title and content concern bandwidth minimization, not C1P augmentation directly. G&J's entry says "Transformation from OPTIMAL LINEAR ARRANGEMENT" and cites [Papadimitriou, 1976a] — the "(a)" suffix disambiguates from Papadimitriou's other 1976 paper ("On the Complexity of Edge Traversing," JACM). The bandwidth paper likely contains the OLA NP-completeness result that feeds into the C1P augmentation reduction, but the issue's citation is misleading — it implies the paper directly proves C1P augmentation NP-completeness.

Hochbaum and Levin (1985): ⚠️ Mentioned for negative approximation results but not listed in the References section. Cannot verify.

Complexity claim: ⚠️ The issue states "O*(2^n) by trying all column permutations." This is incorrect — brute force over all column permutations is O(n!), which grows much faster than O(2^n) for n ≥ 4. For n=6 columns: n! = 720 ≫ 2^6 = 64. No declare_variants! complexity string is proposed.

Well-written

Example Instance 2 is WRONG (confirmed by Python validation):

The NO instance claims the 3×6 matrix with K=0 does NOT have the consecutive ones property:

Row 0: [1, 0, 0, 0, 0, 1]
Row 1: [0, 1, 0, 0, 1, 0]
Row 2: [0, 0, 1, 1, 0, 0]

However, the column permutation (0, 5, 1, 4, 2, 3) yields:

• Row 0: [1, 1, 0, 0, 0, 0] — consecutive ✓
• Row 1: [0, 0, 1, 1, 0, 0] — consecutive ✓
• Row 2: [0, 0, 0, 0, 1, 1] — consecutive ✓

Python validation found 48 permutations achieving C1P with 0 flips. This is a YES instance, not a NO instance.

Example Instance 1 is misleading:

The YES instance with K=4 uses the identity permutation requiring 4 flips. But the optimal permutation (0, 2, 4, 1, 3, 5) achieves C1P with 0 flips — the matrix already has C1P under column reordering. Setting K=4 is correct but makes the instance trivial (any K ≥ 0 works). The example should use a matrix that genuinely requires augmentation.

Python validation stats: 720 total permutations, 264 feasible (≤4 flips), 8 achieve 0 flips. Flip count distribution: 0→8, 1→32, 2→40, 3→48, 4→136 permutations.

Schema inconsistency:

Field	Proposed	Existing models (ConsecutiveOnesSubmatrix, ConsecutiveBlockMinimization)
matrix	Vec<Vec<u8>>	Vec<Vec<bool>>
bound	usize	i64

Should use Vec<Vec<bool>> and i64 for consistency.

Other issues:

• No declare_variants! complexity string proposed
• Missing size field getters (e.g., num_rows, num_cols, num_ones)
• Hochbaum & Levin (1985) reference used in text but absent from References section

Recommendations

• Fix Example 2: Construct a genuine NO instance. A matrix with a Tucker obstruction pattern (e.g., the asteroidal triple pattern) cannot have C1P regardless of column ordering.
• Fix Example 1: Use a matrix that genuinely requires K > 0 augmentation flips under the optimal permutation, so the example exercises the core augmentation structure.
• Fix schema types to match existing consecutive-ones models: Vec<Vec<bool>> and i64.
• Fix complexity claim: O(n!) for brute force over permutations, not O*(2^n). Consider proposing an FPT bound if available.
• Add Hochbaum & Levin (1985) to References or remove the claim.

[isPANN]

Fix-issue changelog

• Schema types fixed: Vec<Vec<u8>> → Vec<Vec<bool>>, usize → i64 (consistency with ConsecutiveOnesSubmatrix and ConsecutiveBlockMinimization)
• Complexity corrected: O*(2^n) → O(n! · m · n) with proper reasoning; added declare_variants! complexity string "factorial(num_cols) * num_rows * num_cols"
• Papadimitriou reference clarified: Added note that [Papadimitriou, 1976a] is the bandwidth paper; the C1P augmentation NP-completeness proof uses a reduction from OLA established in Booth's thesis
• Removed unverified claim: Hochbaum & Levin (1985) approximation result removed (was mentioned in text but not in References)
• Replaced Example 1 (YES): Old 4×6 matrix with K=4 was trivially solvable with 0 flips → New 4×5 graph incidence matrix with K=2 (tight, verified by brute-force over all 120 permutations)
• Replaced Example 2 (NO): Old 3×6 matrix with K=0 was actually a YES instance (48 permutations achieve C1P!) → New 4×4 matrix with K=0 (verified NO: all 24 permutations need ≥1 flip)

Applied by /fix-issue.