[Rule] Optimal Linear Arrangement to Consecutive Ones Matrix Augmentation

[isPANN]

Source: Decision<OptimalLinearArrangement> (decision variant: graph G, bound K)
Target: Consecutive Ones Matrix Augmentation (decision)
Motivation: Establishes NP-completeness of CONSECUTIVE ONES MATRIX AUGMENTATION via polynomial-time reduction from OPTIMAL LINEAR ARRANGEMENT (GT42). The reduction encodes a vertex-ordering problem as a matrix-augmentation problem: given the vertex-edge incidence matrix of the graph, a linear arrangement with total edge length at most K corresponds to a column permutation under which at most K − |E| zero-to-one flips achieve the consecutive ones property.
Reference: Garey & Johnson, Computers and Intractability, problem SR16 (p. 229); transformation from OPTIMAL LINEAR ARRANGEMENT (GT42, p. 200).

Decision-vs-Decision Framing

Both endpoints of this reduction are decision problems with Value = Or:

• Source is Decision<OptimalLinearArrangement>: a graph G = (V, E) plus a decision bound k. It is YES iff G admits a linear arrangement f : V → {1, …, |V|} (a bijection) with total edge length sum_{{u,v} in E} |f(u) − f(v)| ≤ k.
• Target is ConsecutiveOnesMatrixAugmentation: a binary matrix A plus a nonnegative bound bound. It is YES iff some column permutation of A plus at most bound zero-to-one flips yields the consecutive ones property (every row's 1's are contiguous).

The base OptimalLinearArrangement model in the codebase is the optimization variant (Value = Min<usize>, no bound). This reduction is stated against the decision variant Decision<OptimalLinearArrangement>, which carries the bound k. See the Prerequisite section below.

Prerequisite

Decision<OptimalLinearArrangement> is not yet registered in the codebase. The implementation PR for this rule must add it first, following the precedents at src/models/graph/minimum_vertex_cover.rs and src/models/graph/minimum_dominating_set.rs:

1. impl ... DecisionProblemMeta for OptimalLinearArrangement<SimpleGraph> with const DECISION_NAME = "DecisionOptimalLinearArrangement";
2. Inherent getters on Decision<OptimalLinearArrangement<SimpleGraph>>:
   • num_vertices() -> usize (delegates to inner().num_vertices())
   • num_edges() -> usize (delegates to inner().num_edges())
   • k() -> usize (the decision bound, (*self.bound()).try_into().unwrap_or(0))
3. register_decision_variant!(OptimalLinearArrangement<SimpleGraph>, "DecisionOptimalLinearArrangement", ..., size_getters: [("num_vertices", num_vertices), ("num_edges", num_edges)]).

The reduction impl ReduceTo<ConsecutiveOnesMatrixAugmentation> for Decision<OptimalLinearArrangement<SimpleGraph>> then references the getters num_vertices, num_edges, and k.

GJ Source Entry

[SR16] CONSECUTIVE ONES MATRIX AUGMENTATION
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.

Reduction Algorithm

Summary:
Given a Decision<OptimalLinearArrangement> instance (G = (V, E), k), construct a ConsecutiveOnesMatrixAugmentation instance as follows.

Let n = |V| (num_vertices) and m = |E| (num_edges). We build the edge-vertex incidence matrix of G.

1. Matrix construction: Construct the m x n binary matrix A where rows correspond to edges and columns to vertices. For edge e_i = {u, v}, set A[i][u] = 1 and A[i][v] = 1, and all other entries in row i to 0. Each row has exactly two 1's.

2. Bound: Set the target bound = k − m, where k is the source decision bound and m = num_edges. (Handling of k < m and m = 0 is covered under Edge Inputs below.)

3. Intuition: A column permutation is exactly a vertex ordering f : V → {1, …, n}. In row i for edge {u, v}, the two 1's land at positions f(u) and f(v). Making this row consecutive requires filling all 0's strictly between them: |f(u) − f(v)| − 1 flips. Summed over all rows, the augmentation cost under permutation f is sum_{{u,v} in E} (|f(u) − f(v)| − 1) = (sum_{{u,v} in E} |f(u) − f(v)|) − m. This matches the model's per-row cost last − first + 1 − one_count (with one_count = 2, that is |f(u) − f(v)| − 1).

4. Correctness (forward / YES → YES): If G has an arrangement f with sum_{{u,v} in E} |f(u) − f(v)| ≤ k, then using f as the column permutation and filling gaps within each row requires sum |f(u) − f(v)| − m ≤ k − m = bound flips. So the target is YES.

5. Correctness (reverse / YES → YES): If A can be augmented to C1P with at most bound flips, the C1P column permutation defines a vertex ordering f. Each edge row needs |f(u) − f(v)| − 1 flips, so total edge length is flips + m ≤ bound + m = k. So the source decision is YES.

Hence Decision<OptimalLinearArrangement>(G, k) is YES iff ConsecutiveOnesMatrixAugmentation(A, k − m) is YES.

Time complexity of reduction: O(n * m) to construct the incidence matrix.

Edge Inputs

The target model try_new (see src/models/algebraic/consecutive_ones_matrix_augmentation.rs) requires all rows to have equal length and bound ≥ 0; it does not reject a 0-column or 0-row matrix per se, but a 0-row matrix loses the column/vertex identity (num_cols is read from the first row, so a 0 × n matrix reports num_cols = 0). Two degenerate inputs must be handled explicitly:

• Edgeless graph (m = 0). The incidence matrix would be 0 × n, collapsing to a 0-column matrix that erases the vertex arrangement. Since with no edges the total edge length is 0 for every arrangement, the source decision is YES iff k ≥ 0 (always true for the decision bound). Emit a sentinel 1×1 matrix [[false]] with bound = max(0, k): this matrix already has C1P (cost 0 ≤ bound), so the target is trivially YES, preserving the source value. (A 1×1 all-zero matrix is the smallest instance accepted by try_new that keeps num_cols ≥ 1.)

• Negative target bound (k < m). try_new rejects bound < 0. When k < m the source decision is NO (every arrangement costs at least m, since each of the m edges contributes at least 1). Encode a trivially-NO target. Note that ConsecutiveOnesMatrixAugmentation permutes columns, so a single row (or any matrix whose rows can be made simultaneously consecutive by some column permutation) is YES at bound = 0 — a naive [[true, false, true]] would be wrongly accepted with 0 flips after permuting its columns. Instead emit the 3×3 cyclic-overlap matrix [[true, true, false], [false, true, true], [true, false, true]] with bound = 0. Under every of the 6 column permutations the three rows cannot all be made consecutive at once: at least one row's two 1's straddle a 0, so the minimum augmentation cost is 1 > 0 for all permutations. This is a genuine NO at bound = 0, matching the source. The implementation should map any k < m instance to this fixed NO instance.

Note: isolated vertices (degree-0 vertices in a graph with m ≥ 1) are harmless — they simply produce an all-zero column, which is still a valid column and preserves the vertex/column correspondence.

Size Overhead

Symbols (all are real getters on the source Decision<OptimalLinearArrangement>):

• num_vertices = |V|
• num_edges = |E|
• k = the source decision bound

Target metric (code name)	Polynomial (using source getters)
num_rows	num_edges
num_cols	num_vertices
bound	k - num_edges

Derivation: The incidence matrix has one row per edge (num_rows = num_edges) and one column per vertex (num_cols = num_vertices). The augmentation bound is the source decision bound minus the number of edges (bound = k − num_edges), reflecting the baseline cost of 1 flip per edge in any arrangement. (For the degenerate-input sentinels above the actual constructed sizes are the fixed 1×1 / 1×3 matrices; the overhead expressions describe the generic m ≥ 1, k ≥ m case used for asymptotic scaling.)

Validation Method

• Closed-loop test: build a Decision<OptimalLinearArrangement> instance (G, k), reduce to ConsecutiveOnesMatrixAugmentation, solve the target with BruteForce (decision Or), extract the witness column permutation + flips, reconstruct the vertex arrangement on the source, and confirm the source decision value (Or) agrees.
• YES case: path graph P_6 with k = 5. Incidence matrix is 5 × 6, bound = 5 − 5 = 0; the path incidence matrix already has C1P → YES on both sides.
• NO case: the same graph with k = 4 (< m) routes to the fixed 3×3 cyclic-overlap NO sentinel ([[true, true, false], [false, true, true], [true, false, true]], bound = 0, min cost 1 over all column permutations); source decision is NO (every arrangement costs ≥ 5) → NO on both sides.
• Edgeless case: G = ({0,1,2}, ∅), any k. Target is the [[false]] sentinel → YES, matching the always-YES source.

Example

Source instance (Decision<OptimalLinearArrangement>):
Graph G with 6 vertices {0,1,2,3,4,5} and 7 edges:

• Edges: e0={0,1}, e1={1,2}, e2={2,3}, e3={3,4}, e4={4,5}, e5={0,3}, e6={2,5}
• Decision bound k = 11

Constructed target instance (ConsecutiveOnesMatrixAugmentation):
Matrix A (7 × 6), edge-vertex incidence matrix:

       v0 v1 v2 v3 v4 v5
e0:  [  1, 1, 0, 0, 0, 0 ]   (edge {0,1})
e1:  [  0, 1, 1, 0, 0, 0 ]   (edge {1,2})
e2:  [  0, 0, 1, 1, 0, 0 ]   (edge {2,3})
e3:  [  0, 0, 0, 1, 1, 0 ]   (edge {3,4})
e4:  [  0, 0, 0, 0, 1, 1 ]   (edge {4,5})
e5:  [  1, 0, 0, 1, 0, 0 ]   (edge {0,3})
e6:  [  0, 0, 1, 0, 0, 1 ]   (edge {2,5})

Target bound = k − m = 11 − 7 = 4.

Solution mapping (YES):

• Column permutation (arrangement): f(0)=1, f(1)=2, f(2)=3, f(3)=4, f(4)=5, f(5)=6 (identity ordering v0,…,v5).
• Rows e0–e4 already have consecutive 1's (adjacent vertices) → 0 flips each.
• Row e5 (edge {0,3}): 1's at columns 0 and 3, fill positions 1,2 → 2 flips.
• Row e6 (edge {2,5}): 1's at columns 2 and 5, fill positions 3,4 → 2 flips.
• Total flips: 0+0+0+0+0+2+2 = 4 = bound. Target YES.

Verification:

• Total edge length: |1−2|+|2−3|+|3−4|+|4−5|+|5−6|+|1−4|+|3−6| = 1+1+1+1+1+3+3 = 11 = k. Source decision YES (≤ 11).
• Total flips = 11 − 7 = 4 = bound. Consistent.

NO sub-case (same graph, k = 10): bound = 10 − 7 = 3. The minimum augmentation cost over all column permutations equals optimal_OLA − m = 11 − 7 = 4 > 3 (the optimal arrangement cost for this graph is 11, brute-force verified), so the target is NO. Correspondingly the source has no arrangement of total length ≤ 10 → source decision NO. Both sides agree.

References

• [Booth, 1975]: [Booth1975] K. S. Booth (1975). "{PQ} Tree Algorithms". University of California, Berkeley. (Published form: K. S. Booth, "Approximation of the Consecutive Ones Matrix Augmentation Problem," SIAM J. Comput. 14(1):214 (1987), DOI 10.1137/0214052.)
• [Papadimitriou, 1976a]: [Papadimitriou1976a] Christos H. Papadimitriou (1976). "The {NP}-completeness of the bandwidth minimization problem". Computing 16, pp. 263-270. (Companion reference cited by G&J for SR16; the C1MA construction itself is Booth's.)
• [Garey, Johnson, and Stockmeyer, 1976]: [Garey1976g] M. R. Garey and D. S. Johnson and L. Stockmeyer (1976). "Some simplified {NP}-complete graph problems". Theoretical Computer Science 1, pp. 237-267.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from OptimalLinearArrangement to ConsecutiveOnesMatrixAugmentation
Non-trivial	✅ Pass	Encodes vertex ordering as matrix augmentation via incidence matrix construction
Correctness	⚠️ Warn	References are plausible but one citation may be misattributed; decision-vs-optimization mismatch
Well-written	❌ Fail	Overhead table references nonexistent source getter bound; optimization-vs-decision mismatch unaddressed

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. No reduction path currently exists between OptimalLinearArrangement and ConsecutiveOnesMatrixAugmentation in the reduction graph. This is a novel reduction that connects a graph ordering problem to a matrix augmentation problem, which adds value to the reduction topology.

Non-trivial

Pass. The reduction constructs the edge-vertex incidence matrix from the graph and derives a bound transformation (K_C1P = K_OLA - m). This involves genuine structural transformation — encoding a graph ordering problem into a matrix property problem via incidence matrix construction. It is not a simple variable substitution or subtype coercion.

Correctness

Warn. The reduction algorithm itself is mathematically sound and well-known. The correspondence between total edge length in a linear arrangement and the number of 0-to-1 flips needed for the consecutive ones property is correct: for each edge {u,v}, the gap between the two 1's in the incidence matrix row requires |f(u) - f(v)| - 1 flips, and summing over all edges gives (total edge length) - m.

However, there are concerns:

1. [Papadimitriou, 1976a] citation: The issue cites this as "The NP-completeness of the bandwidth minimization problem" (Computing 16, pp. 263-270). The GJ entry SR16 does reference [Papadimitriou, 1976a] for C1MA, but the bandwidth minimization paper primarily addresses bandwidth, not consecutive ones augmentation directly. It is plausible that GJ uses this citation key to encompass related results in the same paper or a companion result, but the mapping is not fully verified. The paper does exist and is real (confirmed via Springer: DOI 10.1007/BF02280884).

2. [Booth, 1975] citation: Correctly identified as K. S. Booth's PhD thesis on PQ-Tree Algorithms at UC Berkeley. This reference is already in the project bibliography (booth1975).

3. [Garey, Johnson, and Stockmeyer, 1976] citation: This paper ("Some simplified NP-complete graph problems", TCS 1, pp. 237-267) proves NP-completeness of OLA as a corollary of Simple Max Cut. However, it is not directly relevant to the OLA → C1MA reduction itself — it establishes the hardness of the source problem, not the reduction. The issue lists it in References but does not cite it in the reduction algorithm, which is appropriate.

4. Decision vs. optimization mismatch: The reduction as described is between decision versions (OLA with bound K_OLA, C1MA with bound K_C1P). However, in this codebase, OptimalLinearArrangement is implemented as an optimization problem (Value = Min<usize>) with no bound parameter, while ConsecutiveOnesMatrixAugmentation is a decision problem with a bound parameter. The issue does not address how this mismatch should be handled in the implementation.

Well-written

Fail. Several issues prevent this from being directly implementable:

1. Overhead table uses nonexistent source getter bound: The overhead expression bound = bound - num_edges references a bound getter on OptimalLinearArrangement, but OLA has no such getter (only num_vertices, num_edges, and graph). The #[reduction(overhead = {...})] macro validates variable names against source getters at compile time, so this would fail. The overhead for num_rows = num_edges and num_cols = num_vertices is correct, but the bound line is invalid.

2. Decision-vs-optimization mismatch not addressed: The reduction algorithm describes a decision-to-decision reduction, but the source problem in the codebase is an optimization problem. The issue should explain how to adapt the reduction: either (a) explain that the reduction maps an OLA optimization instance to a C1MA decision instance by computing the optimal arrangement value and using it as the bound, or (b) propose converting OLA to a decision variant first.

3. Symbol K_OLA undefined in the source problem context: The algorithm references K_OLA as the OLA bound, but since OLA is an optimization problem, there is no such parameter. The symbol should be defined in terms of the optimization objective (e.g., "let K_OLA = the optimal arrangement cost").

4. Validation method references decision-problem workflow: "reduce an OptimalLinearArrangement instance to ConsecutiveOnesMatrixAugmentation, solve target with BruteForce, extract solution" — but this needs clarification on how to set the bound K_C1P when the source is an optimization problem.

5. Example quality: The example is adequately detailed with a fully worked instance (6 vertices, 7 edges) showing the matrix construction, solution mapping, and verification. It exercises the non-trivial cross edges (e5, e6) that require flips. However, the example only demonstrates one arrangement (the identity ordering) and claims it is optimal without proof. For round-trip testing, this is acceptable since brute force can verify optimality, but the example should note that the identity ordering's optimality needs verification.

6. Size overhead field names: The target problem's registered size_fields are num_cols and num_rows. The bound field is a valid getter on the target but is not in size_fields. This may cause issues with the overhead system — the skill cannot verify whether non-size-field getters are accepted in overhead expressions.

Recommendations

• Rewrite the reduction to work with the optimization version of OLA: the reduction constructs the incidence matrix (same as described), but the bound K_C1P should be derived from the source optimization objective, not a decision bound. One approach: implement ReduceTo<ConsecutiveOnesMatrixAugmentation> where the bound is set to the BruteForce-solved optimal value minus m. Alternatively, describe how to use this as an aggregate reduction.
• Remove or fix the bound = bound - num_edges line in the overhead table since bound is not a source getter. If the bound must be part of the reduction, add a note explaining how it should be computed.
• Verify that the identity arrangement is indeed optimal for the example graph (total cost 11) or provide a proof/justification.

[isPANN]

Issue Quality Check — Rule (Re-check, --force)

Previous check (2026-03-26): 2 passed, 1 warning, 1 fail → PoorWritten. This re-check reaches the same verdict after running all 5 Rule Checks including the mandatory Completeness check with literature + codebase + hand-traced corner cases. The blocking bound-getter / decision-vs-optimization issues remain unfixed in the issue body.

Check	Result	Details
Usefulness	✅ Pass	No existing path OptimalLinearArrangement → ConsecutiveOnesMatrixAugmentation (both directions confirmed via pred path)
Non-trivial	✅ Pass	Edge-vertex incidence-matrix construction + bound transformation K_C1P = K_OLA − m; genuine structural encoding
Correctness	⚠️ Warn	Literature real and supports the construction; but decision-vs-optimization model mismatch persists; Papadimitriou-1976a is the bandwidth paper (used by G&J as a companion ref, not the primary C1MA proof)
Completeness	⚠️ Warn	G&J SR16 / Booth (1987) cover all instances with no precondition; traced corner cases preserve the decision value, but edgeless source collapses to a 0-column target matrix and the issue body is silent on edge inputs
Well-written	❌ Fail	Overhead table references a nonexistent source getter bound; decision-vs-optimization mismatch and undefined K_OLA for an optimization source not addressed

Overall: 2 passed, 2 warnings, 1 failed — label PoorWritten retained.

Both models exist in the codebase (no structural blocker):

• Source OptimalLinearArrangement: optimization, Value = Min<usize>, size_fields = [num_edges, num_vertices], getters graph / num_vertices / num_edges (no bound).
• Target ConsecutiveOnesMatrixAugmentation: decision, Value = Or, fields matrix : Vec<Vec<bool>>, bound : i64, getters matrix / bound / num_rows / num_cols.

---

Usefulness — Pass

pred path OptimalLinearArrangement ConsecutiveOnesMatrixAugmentation → "No reduction path" (reverse direction also has none). Novel edge connecting a graph-ordering problem to a matrix-property problem.

Non-trivial — Pass

The reduction builds the m×n edge-vertex incidence matrix and transforms the bound by K_C1P = K_OLA − m. This is a real structural encoding, not a relabeling or subtype coercion.

Correctness — Warn

The mathematical core is sound and I verified it numerically by brute force on the worked example (6 vertices, 7 edges):

• Identity arrangement total edge length = 11 = brute-force optimal OLA cost ✓
• Min augmentation flips over all column permutations = 4 = optimal_OLA − m (11 − 7) ✓
• The model's per-row C1P cost last − first + 1 − one_count equals the issue's |f(u) − f(v)| − 1 for two-1 rows ✓

References:

• [Booth, 1975] — confirmed in docs/paper/references.bib as booth1975 (PQ-Tree Algorithms, UC Berkeley PhD thesis). The published result is Booth, "Approximation of the Consecutive Ones Matrix Augmentation Problem," SIAM J. Comput. 14(1):214 (1987), DOI 10.1137/0214052.
• [Papadimitriou, 1976a] — real paper ("The NP-completeness of the bandwidth minimization problem," Computing 16:263–270, DOI 10.1007/BF02280884), but it is primarily the bandwidth proof; G&J lists it as a companion reference for SR16. The OLA→C1MA construction itself is Booth's.

Remaining concern: the reduction as written is decision→decision (OLA with bound K_OLA, C1MA with bound K_C1P), but in this codebase the source is an optimization problem with no bound. The issue does not say how to bridge this.

Completeness — Warn

5a — Literature (mandatory). G&J Computers and Intractability, SR16 entry (quoted in the issue):

"[SR16] CONSECUTIVE ONES MATRIX AUGMENTATION … 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? … Transformation from OPTIMAL LINEAR ARRANGEMENT."

In G&J both SR16 and the source GT42 OPTIMAL LINEAR ARRANGEMENT are decision problems ("given G and positive integer K, is there an arrangement with total edge length ≤ K?"). The standard incidence-matrix reduction with K_C1P = K_OLA − |E| is stated for any graph instance — no connectivity/simplicity precondition beyond a simple undirected graph (which SimpleGraph already is). So the literature covers all source instances (no hidden precondition → not a Fail on 5a). The OWU npcomplete index corroborates the GT42↔SR16 association; the SIAM paper text is paywalled but the result is the published form of the cited thesis.

5b — Codebase corner cases (hand-traced, not the worked example):

1. Disconnected graph with an isolated vertex — G = ({0,1,2}, {{0,1}}), n=3, m=1. Incidence matrix [[1,1,0]]; column 2 is all-zero. Decision answer correct (min flips 0 = OLA_opt 1 − m 1). Column→vertex extraction still well-defined since every vertex is a column. Pass.
2. Edgeless graph — G = ({0,1,...}, ∅), m=0. Incidence matrix has zero rows; the target model computes num_cols = matrix.first().map_or(0, …), so a k-vertex edgeless graph collapses to a 0×0 matrix, losing the vertex/column identity. The decision/objective value is still correct (cost 0 ≤ any bound), but the column permutation (= vertex arrangement) cannot be reconstructed. This is a degenerate edge input the issue does not discuss.

Existing OLA reductions (optimallineararrangement_ilp.rs, optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs) are both optimization→optimization and carry no bound — reinforcing that an optimization source mapping into a decision target with a fixed bound is the open design question here.

Verdict per rubric: literature covers all instances but the issue body does not state how edge inputs (edgeless / isolated-vertex graphs) are handled → Warn ("works on traced corner cases value-wise; document edge inputs and the degenerate edgeless case").

Well-written — Fail

1. Overhead table uses a nonexistent source getter bound. The line bound = bound − num_edges reads bound from the source OptimalLinearArrangement, which has only graph / num_vertices / num_edges (no bound). #[reduction(overhead = {…})] validates variable names against source getters at compile time → this is a compile error. (num_rows = num_edges, num_cols = num_vertices are correct.)
2. Decision-vs-optimization mismatch not addressed. The algorithm describes a decision→decision reduction, but the source is Min<usize> optimization with no bound parameter. The issue must specify the bridge — e.g., solve OLA optimum and set bound = opt − m (Turing/aggregate flavor), or reduce from a decision variant of OLA.
3. K_OLA undefined for an optimization source. Define it explicitly (e.g., "let K_OLA = the optimal arrangement cost") or via a decision bound.
4. The Validation Method / Example are otherwise solid: the example is correct, non-trivial, and round-trip testable (verified above), with the chord edges e5/e6 forcing flips.

Recommendations

• Fix the overhead table: drop bound = bound − num_edges (it has no valid source getter) and instead document, in prose, how the target bound is computed from the source optimum minus m.
• Choose and state a concrete bridge for the optimization→decision mismatch (most natural: an aggregate/Turing reduction that sets K_C1P = optimal_OLA − m).
• Add an edge-input note covering the edgeless graph (m=0 → 0-column matrix) and isolated vertices.

[isPANN]

Issue body rewritten — framing fixed

Addressed all blocking/substantive items from the latest /check-issue report:

1. Reframed as Decision<OptimalLinearArrangement> → ConsecutiveOnesMatrixAugmentation (decision → decision, Or → Or). The source now carries a decision bound k; YES iff total edge length ≤ k. Removed the optimization-vs-decision mismatch entirely.
2. Added a "Prerequisite" subsection. Decision<OptimalLinearArrangement> is not yet registered; the implementation PR must add it via DecisionProblemMeta + inherent num_vertices()/num_edges()/k() getters + register_decision_variant!, following the minimum_vertex_cover.rs / minimum_dominating_set.rs precedents.
3. Fixed the overhead table to reference only real source getters of Decision<OptimalLinearArrangement>: num_rows = num_edges, num_cols = num_vertices, bound = k - num_edges. Removed the bogus bound = bound - num_edges line (no bound getter exists on the source).
4. Removed the undefined K_OLA symbol — now uses the decision bound k consistently throughout.
5. Added an "Edge Inputs" subsection. Verified ConsecutiveOnesMatrixAugmentation::try_new (requires equal row lengths and bound ≥ 0; num_cols is read from the first row). Specified sentinels:
   • m = 0 (edgeless): the 0 × n incidence matrix would erase column/vertex identity, so emit [[false]] with bound = max(0, k) → trivially YES, matching the always-YES source.
   • k < m (would force negative bound, rejected by try_new): map to a fixed trivially-NO instance, matching the NO source (every arrangement costs ≥ m).
   • Isolated vertices (degree 0, m ≥ 1) are harmless: they yield an all-zero column that still preserves the correspondence.
6. Kept the verified worked example but reframed it under the decision source: k = 11 gives target bound = 4 → both sides YES; added a k = 10 sub-case (target bound = 3 < 4) → both sides NO.

References left intact (Booth 1975/1987, Papadimitriou 1976a as G&J companion ref, Garey-Johnson-Stockmeyer 1976), with the Booth 1987 SIAM published form noted as the primary C1MA proof.

[isPANN]

Issue Quality Check — Rule (Re-check, --force)

Third pass after the 2026-05-28 rewrite that reframed the rule as Decision<OptimalLinearArrangement> → ConsecutiveOnesMatrixAugmentation (decision → decision, Or → Or). The reframing fixed the previously-fatal bound-getter / optimization-vs-decision blocker. All 5 Rule Checks were run, including the mandatory Completeness check with literature + codebase + hand-traced corner cases and a Python verification of the model semantics. However, a new fatal bug was found in the k < m edge-case sentinel — see Completeness/Correctness below.

Check	Result	Details
Usefulness	✅ Pass	No existing path Decision<OptimalLinearArrangement> → ConsecutiveOnesMatrixAugmentation
Non-trivial	✅ Pass	Edge-vertex incidence-matrix construction + bound transform bound = k − num_edges; genuine structural encoding
Correctness	❌ Fail	Core construction + bound mapping verified correct, but the k < m NO-sentinel [[true, false, true]] actually evaluates to YES under the model's column-permutation semantics, inverting the answer for every k < m instance
Completeness	❌ Fail	Literature covers all instances, main case + m = 0 sentinel + isolated vertices verified, but the k < m corner case is broken (single-row matrices can never be NO instances)
Well-written	✅ Pass	Overhead table now references only real source getters; prerequisite, symbols, and example are clear

Overall: 3 passed, 2 failed — adding label Wrong (and the construction is incomplete on a legitimate corner case). The reframing resolved PoorWritten; removing that label.

Both endpoints are now decision problems (Value = Or). The source Decision<OptimalLinearArrangement> is not yet registered (prerequisite correctly stated); the target ConsecutiveOnesMatrixAugmentation exists with fields = matrix : Vec<Vec<bool>>, bound : i64, getters matrix / bound / num_rows / num_cols.

---

Usefulness — Pass

pred path OptimalLinearArrangement ConsecutiveOnesMatrixAugmentation → "No reduction path"; the Decision<...> source is not registered, so no path can exist yet. Novel edge connecting a graph-ordering decision problem to a matrix-property decision problem. (G&J SR16 is established via exactly this transformation from OPTIMAL LINEAR ARRANGEMENT.)

Non-trivial — Pass

Builds the m × n edge-vertex incidence matrix and transforms the bound by bound = k − num_edges. Genuine structural encoding, not a relabeling or subtype coercion.

Correctness — Fail

The main construction and bound mapping are CORRECT — verified numerically. I confirmed against the actual model semantics in src/models/algebraic/consecutive_ones_matrix_augmentation.rs:

• Orientation is right. The model's dims() returns vec![num_cols; num_cols] and validate_permutation confirms the config is a permutation of columns. row_augmentation_cost(row, config) = last − first + 1 − one_count is computed per row under the column permutation. With rows = edges and columns = vertices, a two-1 edge row at vertices u,v costs |f(u) − f(v)| + 1 − 2 = |f(u) − f(v)| − 1. ✅ matches the issue's claim and the OLA edge-length objective.
• Overhead orientation matches the built matrix: num_rows = num_edges, num_cols = num_vertices. ✅
• Bound mapping bound = k − num_edges verified by brute force on the worked example (6 vertices, 7 edges): min flips over all column permutations = 4 = min_OLA (11) − m (7). k = 11 → bound = 4: source YES / target YES. k = 10 → bound = 3: source NO / target NO. ✅

Fatal bug — the k < m sentinel inverts the answer. The "Edge Inputs" section maps every k < m instance to the fixed matrix [[true, false, true]] with bound = 0, claiming "the two 1's straddle a 0 and need 1 flip > 0", i.e. a NO instance. This is false under the model's semantics, because the model permutes columns. Brute-forcing all column permutations of [[true, false, true]]:

perm (0,1,2) cost 1
perm (0,2,1) cost 0   <-- columns 0 and 2 become adjacent, 0 flips
perm (1,0,2) cost 0
...

So [[true, false, true]] with bound = 0 evaluates to YES, but the source decision when k < m is NO. The reduction therefore returns the wrong answer for every k < m source instance. More fundamentally: no single-row matrix can ever be a NO instance — any single row of 1's can always be made consecutive with 0 flips by permuting its columns together (exhaustively confirmed for all rows up to width 4).

The fix: a correct trivially-NO sentinel needs ≥ 3 rows forming an interval/asteroidal obstruction. The smallest is the 3×3 cyclic-overlap matrix

[[true,  true,  false],
 [false, true,  true ],
 [true,  false, true ]]

with bound = 0, which is NO at bound 0 (verified: every column permutation costs ≥ 1) and would correctly encode the NO source.

References (real, unchanged from prior check): booth1975 is in docs/paper/references.bib (the published C1MA result is Booth, SIAM J. Comput. 14(1):214, 1987, DOI 10.1137/0214052); Papadimitriou 1976a is the real bandwidth paper that G&J lists as a companion reference for SR16. No fabricated citations.

Completeness — Fail

5a — Literature (mandatory). G&J Computers and Intractability SR16 (quoted in the issue) states the 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?" with "Transformation from OPTIMAL LINEAR ARRANGEMENT." Both SR16 and the source GT42 are decision problems in G&J, so the decision→decision framing is the literature-faithful one, and the incidence-matrix construction with K_C1P = K_OLA − |E| is stated for any simple graph (no connectivity/simplicity precondition beyond SimpleGraph). So 5a is clean — the literature covers all source instances.

5b — Codebase corner cases (hand-traced against consecutive_ones_matrix_augmentation.rs):

1. Disconnected graph + isolated vertex — G = ({0,1,2}, {{0,1}}), n=3, m=1, k=1 → bound=0. Incidence matrix [[1,1,0]]; column 2 all-zero. Min flips 0 ≤ 0 → target YES; source OLA opt = 1 ≤ 1 → YES. ✅ Isolated vertices are harmless (all-zero column preserved). Matches the issue's claim.
2. Edgeless graph (m = 0) — sentinel [[false]] with bound = max(0, k). Verified: [[false]] has C1P with cost 0 ≤ bound → YES, matching the always-YES source (total edge length 0). ✅ Correct.
3. k < m (negative target bound) — BROKEN. As shown in Correctness, the proposed [[true, false, true]]/bound = 0 sentinel evaluates YES, not NO, so the reduction produces the wrong decision value for the entire k < m family (a legitimate, common corner case — e.g., the issue's own k = 4 validation case for P_6). This is a Completeness Fail: the algorithm produces an invalid (answer-inverting) target on a legitimate corner case.

Existing OLA reductions (optimallineararrangement_ilp.rs, optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs) are optimization→optimization and don't bear on the decision-sentinel design.

Well-written — Pass

The rewrite fixed the prior blockers:

• Overhead table now uses only real Decision<OptimalLinearArrangement> getters: num_rows = num_edges, num_cols = num_vertices, bound = k − num_edges (the bogus bound = bound − num_edges line is gone).
• The Prerequisite subsection correctly specifies Decision<OptimalLinearArrangement> registration via DecisionProblemMeta + inherent num_vertices()/num_edges()/k() getters + register_decision_variant!, matching the minimum_vertex_cover.rs / minimum_dominating_set.rs precedents exactly (confirmed the k() pattern (*self.bound()).try_into().unwrap_or(0) and the size_getters form).
• K_OLA is gone; the decision bound k is used consistently. The worked example is correct, non-trivial, and round-trip testable (chord edges e5/e6 force the flips).

Note: the overhead getters num_vertices, num_edges, k only exist once the prerequisite registration adds them as inherent methods on Decision<OptimalLinearArrangement<SimpleGraph>> — they are not present on main today. The issue states this dependency clearly, so this is informational, not a defect.

Recommendations

• Fix the k < m sentinel (blocking): replace the answer-inverting [[true, false, true]]/bound = 0 with a genuine NO instance, e.g. the 3×3 cyclic-overlap matrix above with bound = 0 (or any matrix with a verified C1P obstruction at the chosen bound). Add a one-line note that single-row matrices can never be NO instances under column permutation, to prevent the same mistake recurring.
• Re-state the m = 0 and k < m sentinels as small unit assertions in the planned closed-loop test so the inversion bug can't slip through implementation.