problemreductions/rules/
bmf_bicliquecover.rs

1//! Reduction from BMF (exact Boolean Matrix Factorization) to BicliqueCover.
2//!
3//! Classical equivalence (Monson, Pullman, Rees 1995): an m x n boolean
4//! matrix `A` is the biadjacency matrix of the bipartite graph `G_A`, and
5//! each rank-1 factor of `A = B ⊙ C` is exactly a (complete) biclique of
6//! `G_A` — its left side is `{i : B[i][r] = 1}` and its right side is
7//! `{j : C[r][j] = 1}`. Hence an exact rank-`k` factorization corresponds
8//! to a cover of `E(G_A)` by `k` sub-bicliques of `G_A`, and the total
9//! factor weight `|B|_1 + |C|_1` equals the total biclique size (the
10//! number of vertex memberships summed over all bicliques).
11//!
12//! Variable-layout mapping: BMF stores `B` row-major followed by `C`
13//! row-major, while BicliqueCover stores vertex memberships vertex-major.
14//! `extract_solution` transposes the right-vertex half so the extracted
15//! BMF config matches `B` and `C`.
16
17use crate::models::algebraic::BMF;
18use crate::models::graph::BicliqueCover;
19use crate::reduction;
20use crate::rules::traits::{ReduceTo, ReductionResult};
21use crate::topology::BipartiteGraph;
22
23/// Convert a BicliqueCover config (vertex-major: index `v*k + b`) to a BMF
24/// config (B row-major at `[0, m*k)` then C row-major at `[m*k, m*k + k*n)`).
25///
26/// The left half copies unchanged; the right half transposes from
27/// vertex-major `(m+j)*k + l` to biclique-row-major `m*k + l*n + j`.
28pub(crate) fn config_bc_to_bmf(bc: &[usize], m: usize, n: usize, k: usize) -> Vec<usize> {
29    let mut bmf = vec![0usize; m * k + k * n];
30    for i in 0..m {
31        for l in 0..k {
32            bmf[i * k + l] = bc[i * k + l];
33        }
34    }
35    for l in 0..k {
36        for j in 0..n {
37            bmf[m * k + l * n + j] = bc[(m + j) * k + l];
38        }
39    }
40    bmf
41}
42
43/// Inverse of [`config_bc_to_bmf`]: BMF config (B row-major then C row-major)
44/// to BicliqueCover config (vertex-major).
45pub(crate) fn config_bmf_to_bc(bmf: &[usize], m: usize, n: usize, k: usize) -> Vec<usize> {
46    let mut bc = vec![0usize; (m + n) * k];
47    for i in 0..m {
48        for l in 0..k {
49            bc[i * k + l] = bmf[i * k + l];
50        }
51    }
52    for l in 0..k {
53        for j in 0..n {
54            bc[(m + j) * k + l] = bmf[m * k + l * n + j];
55        }
56    }
57    bc
58}
59
60/// Result of reducing BMF to BicliqueCover.
61#[derive(Debug, Clone)]
62pub struct ReductionBMFToBicliqueCover {
63    target: BicliqueCover,
64    m: usize,
65    n: usize,
66    k: usize,
67}
68
69impl ReductionResult for ReductionBMFToBicliqueCover {
70    type Source = BMF;
71    type Target = BicliqueCover;
72
73    fn target_problem(&self) -> &BicliqueCover {
74        &self.target
75    }
76
77    /// Map a BicliqueCover config (vertex-major) back to a BMF config (B row-major, then C row-major).
78    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
79        config_bc_to_bmf(target_solution, self.m, self.n, self.k)
80    }
81}
82
83#[reduction(
84    overhead = {
85        num_vertices = "rows + cols",
86        num_edges = "rows * cols",
87        rank = "rank",
88    }
89)]
90impl ReduceTo<BicliqueCover> for BMF {
91    type Result = ReductionBMFToBicliqueCover;
92
93    fn reduce_to(&self) -> Self::Result {
94        let m = self.rows();
95        let n = self.cols();
96        let k = self.rank();
97        let mut edges = Vec::new();
98        for (i, row) in self.matrix().iter().enumerate() {
99            for (j, &val) in row.iter().enumerate() {
100                if val {
101                    edges.push((i, j));
102                }
103            }
104        }
105        let target = BicliqueCover::new(BipartiteGraph::new(m, n, edges), k);
106        ReductionBMFToBicliqueCover { target, m, n, k }
107    }
108}
109
110#[cfg(feature = "example-db")]
111pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
112    use crate::export::SolutionPair;
113
114    vec![crate::example_db::specs::RuleExampleSpec {
115        id: "bmf_to_bicliquecover",
116        build: || {
117            // 2x2 all-ones, rank 1 — a single biclique covering both sides exactly.
118            let source = BMF::new(vec![vec![true, true], vec![true, true]], 1);
119            crate::example_db::specs::rule_example_with_witness::<_, BicliqueCover>(
120                source,
121                SolutionPair {
122                    // BMF config (B row-major, C row-major): B = [[1],[1]], C = [[1,1]]
123                    source_config: vec![1, 1, 1, 1],
124                    // BicliqueCover config (vertex-major, k=1): v0, v1 (left), v2, v3 (right) all in biclique 0
125                    target_config: vec![1, 1, 1, 1],
126                },
127            )
128        },
129    }]
130}
131
132#[cfg(test)]
133#[path = "../unit_tests/rules/bmf_bicliquecover.rs"]
134mod tests;
problemreductions/rules/bmf_bicliquecover.rs

problemreductions/rules/
bmf_bicliquecover.rs
