problemreductions/rules/
optimallineararrangement_consecutiveonesmatrixaugmentation.rs

1//! Reduction from Decision Optimal Linear Arrangement to Consecutive Ones
2//! Matrix Augmentation.
3//!
4//! Establishes NP-completeness of CONSECUTIVE ONES MATRIX AUGMENTATION
5//! (Garey & Johnson SR16) via transformation from OPTIMAL LINEAR ARRANGEMENT
6//! (GT42). Given `Decision<OptimalLinearArrangement>(G, k)`, the edge-vertex
7//! incidence matrix `A` of `G` has rows = edges and columns = vertices. A
8//! column permutation is exactly a vertex ordering `f`; making each edge row
9//! consecutive costs `|f(u) - f(v)| - 1` flips, so the total augmentation cost
10//! equals `(total edge length) - |E|`. Hence the source is YES iff
11//! `ConsecutiveOnesMatrixAugmentation(A, k - |E|)` is YES.
12
13use crate::models::algebraic::ConsecutiveOnesMatrixAugmentation;
14use crate::models::decision::Decision;
15use crate::models::graph::OptimalLinearArrangement;
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18use crate::topology::{Graph, SimpleGraph};
19
20/// Which construction branch produced the target instance.
21#[derive(Debug, Clone)]
22enum ConstructionKind {
23    /// Edgeless source (`m = 0`): always-YES `[[false]]` sentinel.
24    /// Carries the source vertex count to reconstruct an identity arrangement.
25    EdgelessYes { num_vertices: usize },
26    /// `k < m`: genuine-NO 3x3 cyclic-overlap sentinel.
27    FixedNo { num_vertices: usize },
28    /// Generic incidence-matrix construction (`m >= 1`, `k >= m`).
29    Incidence { num_vertices: usize },
30}
31
32/// Result of reducing `Decision<OptimalLinearArrangement<SimpleGraph>>` to
33/// `ConsecutiveOnesMatrixAugmentation`.
34#[derive(Debug, Clone)]
35pub struct ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
36    target: ConsecutiveOnesMatrixAugmentation,
37    construction: ConstructionKind,
38}
39
40impl ReductionResult for ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
41    type Source = Decision<OptimalLinearArrangement<SimpleGraph>>;
42    type Target = ConsecutiveOnesMatrixAugmentation;
43
44    fn target_problem(&self) -> &Self::Target {
45        &self.target
46    }
47
48    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
49        match &self.construction {
50            // No edges: any arrangement has total length 0 <= k, so emit the
51            // identity arrangement f(v) = v over all source vertices.
52            ConstructionKind::EdgelessYes { num_vertices } => (0..*num_vertices).collect(),
53            // Genuine NO: there is no valid arrangement; return a sentinel
54            // (identity) so the source decision evaluates correctly (NO).
55            ConstructionKind::FixedNo { num_vertices } => (0..*num_vertices).collect(),
56            ConstructionKind::Incidence { num_vertices } => {
57                // The C1MA witness is a column permutation: `config[position] = col`.
58                // Columns correspond to vertices, so this places vertex `col` at
59                // `position`. The OLA arrangement is `f(vertex) = position`, i.e.
60                // the inverse permutation.
61                let n = *num_vertices;
62                if target_solution.len() != n {
63                    return (0..n).collect();
64                }
65                let mut arrangement = vec![0usize; n];
66                let mut seen = vec![false; n];
67                for (position, &vertex) in target_solution.iter().enumerate() {
68                    if vertex >= n || seen[vertex] {
69                        // Not a valid permutation; fall back to identity.
70                        return (0..n).collect();
71                    }
72                    seen[vertex] = true;
73                    arrangement[vertex] = position;
74                }
75                arrangement
76            }
77        }
78    }
79}
80
81/// The fixed 3x3 cyclic-overlap NO sentinel: under every column permutation at
82/// least one row's two 1's straddle a 0, so the minimum augmentation cost is
83/// `1 > 0`.
84fn no_sentinel() -> ConsecutiveOnesMatrixAugmentation {
85    ConsecutiveOnesMatrixAugmentation::new(
86        vec![
87            vec![true, true, false],
88            vec![false, true, true],
89            vec![true, false, true],
90        ],
91        0,
92    )
93}
94
95#[reduction(
96    overhead = {
97        num_rows = "num_edges",
98        num_cols = "num_vertices",
99        bound = "k - num_edges",
100    }
101)]
102impl ReduceTo<ConsecutiveOnesMatrixAugmentation>
103    for Decision<OptimalLinearArrangement<SimpleGraph>>
104{
105    type Result = ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation;
106
107    fn reduce_to(&self) -> Self::Result {
108        let n = self.num_vertices();
109        let m = self.num_edges();
110        let k = self.k();
111
112        // Edgeless graph: total edge length is 0 for every arrangement, so the
113        // source decision is YES for any bound. Emit a 1x1 all-zero matrix
114        // (already C1P at cost 0 <= bound) to keep num_cols >= 1.
115        if m == 0 {
116            return ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
117                target: ConsecutiveOnesMatrixAugmentation::new(vec![vec![false]], k as i64),
118                construction: ConstructionKind::EdgelessYes { num_vertices: n },
119            };
120        }
121
122        // Negative target bound (k < m): every arrangement costs at least m
123        // (each edge contributes >= 1), so the source decision is NO. Route to
124        // the fixed genuine-NO sentinel.
125        if k < m {
126            return ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
127                target: no_sentinel(),
128                construction: ConstructionKind::FixedNo { num_vertices: n },
129            };
130        }
131
132        // Generic case: edge-vertex incidence matrix, rows = edges, cols = vertices.
133        let mut matrix = vec![vec![false; n]; m];
134        for (edge_idx, (u, v)) in self.inner().graph().edges().into_iter().enumerate() {
135            matrix[edge_idx][u] = true;
136            matrix[edge_idx][v] = true;
137        }
138        let bound = (k - m) as i64;
139
140        ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
141            target: ConsecutiveOnesMatrixAugmentation::new(matrix, bound),
142            construction: ConstructionKind::Incidence { num_vertices: n },
143        }
144    }
145}
146
147#[cfg(feature = "example-db")]
148pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
149    use crate::export::SolutionPair;
150
151    vec![crate::example_db::specs::RuleExampleSpec {
152        id: "optimallineararrangement_to_consecutiveonesmatrixaugmentation",
153        build: || {
154            use crate::example_db::specs::assemble_rule_example;
155
156            // 6 vertices, 7 edges (path + two chords). Optimal arrangement
157            // [0,1,2,3,4,5] has total edge length 11; with k = 11 the target
158            // bound is 11 - 7 = 4 and the identity column permutation works.
159            let source = Decision::new(
160                OptimalLinearArrangement::new(SimpleGraph::new(
161                    6,
162                    vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 3), (2, 5)],
163                )),
164                11,
165            );
166            let reduction = ReduceTo::<ConsecutiveOnesMatrixAugmentation>::reduce_to(&source);
167            // Source arrangement f(v) = v <=> target column permutation = identity.
168            let source_config = vec![0, 1, 2, 3, 4, 5];
169            let target_config = vec![0, 1, 2, 3, 4, 5];
170            assemble_rule_example(
171                &source,
172                reduction.target_problem(),
173                vec![SolutionPair {
174                    source_config,
175                    target_config,
176                }],
177            )
178        },
179    }]
180}
181
182#[cfg(test)]
183#[path = "../unit_tests/rules/optimallineararrangement_consecutiveonesmatrixaugmentation.rs"]
184mod tests;
problemreductions/rules/optimallineararrangement_consecutiveonesmatrixaugmentation.rs

problemreductions/rules/
optimallineararrangement_consecutiveonesmatrixaugmentation.rs
