[Model] ConsecutiveOnesSubmatrix

[isPANN]

Motivation

CONSECUTIVE ONES SUBMATRIX from Garey & Johnson, A4 SR14. A classical NP-complete problem in combinatorial matrix theory. The consecutive ones property (C1P) -- that the columns of a binary matrix can be permuted so that all 1's in each row are contiguous -- is fundamental in computational biology (DNA physical mapping), interval graph recognition, and PQ-tree algorithms. While testing whether a full matrix has the C1P is polynomial (Booth and Lueker, 1976), finding the largest column subset with this property is NP-hard. The problem connects to interval graph theory: a binary matrix has the C1P if and only if the corresponding hypergraph is an interval hypergraph.

Associated rules:

• R108: Hamiltonian Path -> Consecutive Ones Submatrix (this model is the target)

Prerequisite note: The source rule R108 requires a HamiltonianPath model, which does not yet exist in the codebase. This model can be implemented independently, but the reduction rule R108 must wait for HamiltonianPath.

Definition

Name: ConsecutiveOnesSubmatrix
Canonical name: CONSECUTIVE ONES SUBMATRIX
Reference: Garey & Johnson, Computers and Intractability, A4 SR14, p.229

Mathematical definition:

INSTANCE: An m x n matrix A of 0's and 1's and a positive integer K <= n.
QUESTION: Is there an m x K submatrix B of A (formed by selecting K columns) that has the "consecutive ones" property, i.e., such that the columns of B can be permuted so that in each row all the 1's occur consecutively?

Variables

• Count: n binary variables (one per column, indicating whether that column is selected) plus a permutation of the selected K columns.
• Per-variable domain: Column selection: {0, 1} for each of the n columns. Column ordering: a permutation of the K selected columns.
• Meaning: The binary variable c_j = 1 means column j is included in the submatrix B. The permutation pi defines the column ordering of B. The constraint is that exactly K columns are selected and, under permutation pi, every row's 1-entries are contiguous.
• dims() specification: vec![2; n] where n = number of columns. Each variable is binary (include column or not). The permutation aspect is handled internally by evaluate, which tests all K! orderings of the selected columns for the C1P.

Schema (data type)

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

Field	Type	Description
matrix	Vec<Vec<bool>>	The m x n binary matrix A
bound_k	usize	Required number of columns K for the submatrix

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

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

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed.
• The optimization variant (maximize K) is also NP-hard.
• When K = n, the problem reduces to testing whether the full matrix has the C1P, which is solvable in O(m + n + sum of 1-entries) time using PQ-trees (Booth and Lueker, 1976).

Complexity

• Best known exact algorithm: Brute-force: enumerate all (n choose K) column subsets, test each for C1P using Booth-Lueker's linear-time PQ-tree algorithm. Total: O(C(n,K) * (m + n)). For general instances, this is exponential.
• Fixed-parameter tractability: The problem is FPT when parameterized by the number of columns to delete (n - K). Dom et al. (2010) gave FPT algorithms for several consecutive ones submatrix variants.
• NP-completeness: NP-complete [Booth, 1975], via transformation from HAMILTONIAN PATH. Remains NP-hard for (2,3)-matrices and (3,2)-matrices.
• Polynomial special case: K = n: solvable in O(m + n + f) time where f is the number of 1-entries, using PQ-trees [Booth and Lueker, 1976].
• declare_variants! complexity string: "2^(num_cols) * num_rows" (brute-force column subset enumeration with C1P test).
• References:
  • K. S. Booth (1975). "PQ Tree Algorithms." Ph.D. Thesis, UC Berkeley.
  • K. S. Booth and G. S. Lueker (1976). "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms." JCSS 13, pp. 335-379.
  • M. Dom, J. Guo, and R. Niedermeier (2010). "Approximation and fixed-parameter algorithms for consecutive ones submatrix problems." JCSS 76, pp. 204-221.

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 an m x K submatrix B of A that has the "consecutive ones" property, i.e., such that the columns of B can be permuted so that in each row all the 1's occur consecutively?
Reference: [Booth, 1975]. Transformation from HAMILTONIAN PATH.
Comment: The variant in which we ask instead that B have the "circular ones" property, i.e., that the columns of B can be permuted so that in each row either all the 1's or all the 0's occur consecutively, is also NP-complete. Both problems can be solved in polynomial time if K = n (in which case we are asking if A has the desired property), e.g., see [Fulkerson and Gross, 1965], [Tucker, 1971], and [Booth and Lueker, 1976].

Related variants:

• Circular ones property: same as C1P but allowing wrap-around (also NP-complete for the submatrix selection problem).
• Consecutive ones editing: minimum number of 0->1 or 1->0 flips to make a matrix have the C1P (NP-hard).
• Row deletion variant: minimum number of rows to delete to achieve C1P (NP-hard).

How to solve

• It can be solved by (existing) bruteforce -- enumerate all (n choose K) column subsets, test each for C1P.
• It can be solved by reducing to integer programming -- binary variable for each column selection, add constraints encoding the C1P (using auxiliary variables for column ordering and interval endpoints).
• Other: FPT algorithms parameterized by n-K (Dom et al., 2010). Heuristic approaches using PQ-trees with branch-and-bound.

Example Instance

Instance 1 (YES, has C1P submatrix with K=5):
Matrix A (6 x 8):

	c1	c2	c3	c4	c5	c6	c7	c8
r1	1	0	0	0	0	1	0	0
r2	1	1	0	0	0	0	0	1
r3	0	0	1	0	0	0	1	0
r4	0	1	1	0	0	0	0	0
r5	0	0	0	1	1	0	0	0
r6	0	0	0	0	1	1	0	0

K = 5.

Select columns {c1, c2, c3, c5, c6}. Under column permutation [c5, c6, c1, c2, c3]:

	c5	c6	c1	c2	c3
r1	0	1	1	0	0
r2	0	0	1	1	0
r3	0	0	0	0	1
r4	0	0	0	1	1
r5	1	0	0	0	0
r6	1	1	0	0	0

All rows have consecutive 1's. Answer: YES.

Instance 2 (NO for K=4, YES for K=3):
Matrix A (3 x 4), the "Tucker matrix" pattern:

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

K = 4 (full matrix): No column permutation makes all 1's consecutive in every row simultaneously (Tucker obstruction). Answer: NO for K=4.

For K = 3, selecting columns {c1, c2, c4} with permutation [c2, c1, c4]:

	c2	c1	c4
r1	1	1	1
r2	0	1	1
r3	1	0	0

Answer: YES for K=3.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem with applications in computational biology and interval graph theory
Non-trivial	✅ Pass	Distinct from all existing problems -- combines column selection with permutation ordering constraint
Correctness	⚠️ Warn	Dom et al. publication year is 2010, not 2014 as cited; volume is 76, not 76(4)
Well-written	⚠️ Warn	Example 1 has a failed first attempt visible in text; otherwise well-structured

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

ConsecutiveOnesSubmatrix does not exist in the codebase. The problem has strong practical motivation in computational biology (DNA physical mapping), interval graph recognition, and PQ-tree algorithms. It has an associated reduction rule (R108: Hamiltonian Path -> Consecutive Ones Submatrix), giving it connectivity in the reduction graph. The connection between the consecutive ones property and interval hypergraphs adds theoretical value. Pass.

Non-trivial

The problem is genuinely distinct from all existing problems. The feasibility constraint combines two aspects: (1) selecting a subset of K columns, and (2) finding a permutation of those columns such that every row's 1-entries are contiguous. This is structurally different from SAT, graph problems, set problems, and matrix problems already in the codebase (QUBO, ILP, BMF). The variable structure (binary column selection + permutation ordering) is unique. Pass.

Correctness

• Booth (1975): Confirmed. Kellogg S. Booth, "PQ-Tree Algorithms," Ph.D. Thesis, University of California, Berkeley, 1975. Available via OSTI.GOV and as PDF (UCRL-51953).
• 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. Correct venue, volume, and page numbers.
• Dom, Guo, and Niedermeier: The paper exists but the year is 2010, not 2014. The correct citation is: "Approximation and fixed-parameter algorithms for consecutive ones submatrix problems," JCSS 76, pp. 204-221, 2010. The volume number cited in the issue (76(4)) appears incorrect -- it is volume 76, pages 204-221.
• NP-completeness via Hamiltonian Path: Consistent with Garey & Johnson and the Booth thesis.
• Tan and Zhang (2007) 2-approximation: Not independently verified. This reference is mentioned in the Complexity section but not in the References list.

Well-written

Strengths:

• Mathematical definition is precise and faithful to Garey & Johnson
• Variables section correctly identifies both the column selection and permutation aspects
• Schema is clean and appropriate
• Extra Remark section adds useful context about circular ones variant and related problems
• Example Instance 1 eventually arrives at a correct, verified solution
• Example Instance 2 (Tucker matrix) is a good NO instance, and the K=3 YES answer is correctly verified

Minor issues:

• Example 1 contains a failed first attempt (permutation [c6,c1,c2,c3,c5] fails for r6) before finding the correct permutation. This should be cleaned up for clarity.
• The "Tan and Zhang (2007)" reference is mentioned but not listed in the References section.
• No concrete declare_variants! complexity string is proposed.

Recommendations

• Fix the Dom et al. year from 2014 to 2010 and the volume citation from 76(4) to 76.
• Add the Tan and Zhang reference to the References section or remove the claim.
• Clean up Example 1 to present only the working permutation.
• Propose a concrete complexity string for declare_variants!.