problemreductions/rules/
bicliquecover_bmf.rs

1//! Reduction from BicliqueCover to BMF (exact Boolean Matrix Factorization).
2//!
3//! Inverse of [`crate::rules::bmf_bicliquecover`]: a bipartite graph
4//! `G = (L, R, E)` is encoded by its `|L| × |R|` biadjacency matrix
5//! `A_G` with `A_G[i][j] = 1` iff `(i, j) ∈ E`. Under the classical
6//! sub-biclique semantics, a biclique cover of `G` by `k` sub-bicliques
7//! is exactly an exact rank-`k` Boolean factorization of `A_G`, and the
8//! total biclique size equals `|B|_1 + |C|_1`.
9//!
10//! Layout mapping is the inverse transpose from the forward reduction —
11//! the shared helpers [`super::bmf_bicliquecover::config_bmf_to_bc`] and
12//! `config_bc_to_bmf` live in the sibling module.
13
14use crate::models::algebraic::BMF;
15use crate::models::graph::BicliqueCover;
16use crate::reduction;
17use crate::rules::bmf_bicliquecover::config_bmf_to_bc;
18use crate::rules::traits::{ReduceTo, ReductionResult};
19
20/// Result of reducing BicliqueCover to BMF.
21#[derive(Debug, Clone)]
22pub struct ReductionBicliqueCoverToBMF {
23    target: BMF,
24    m: usize,
25    n: usize,
26    k: usize,
27}
28
29impl ReductionResult for ReductionBicliqueCoverToBMF {
30    type Source = BicliqueCover;
31    type Target = BMF;
32
33    fn target_problem(&self) -> &BMF {
34        &self.target
35    }
36
37    /// Map a BMF config (B row-major, C row-major) to a BicliqueCover
38    /// config (vertex-major) via the inverse transpose.
39    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
40        config_bmf_to_bc(target_solution, self.m, self.n, self.k)
41    }
42}
43
44#[reduction(
45    overhead = {
46        rows = "left_size",
47        cols = "right_size",
48        rank = "rank",
49    }
50)]
51impl ReduceTo<BMF> for BicliqueCover {
52    type Result = ReductionBicliqueCoverToBMF;
53
54    fn reduce_to(&self) -> Self::Result {
55        let m = self.left_size();
56        let n = self.right_size();
57        let k = self.k();
58        let mut matrix = vec![vec![false; n]; m];
59        for &(i, j) in self.graph().left_edges() {
60            matrix[i][j] = true;
61        }
62        let target = BMF::new(matrix, k);
63        ReductionBicliqueCoverToBMF { target, m, n, k }
64    }
65}
66
67#[cfg(feature = "example-db")]
68pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
69    use crate::export::SolutionPair;
70    use crate::topology::BipartiteGraph;
71
72    vec![crate::example_db::specs::RuleExampleSpec {
73        id: "bicliquecover_to_bmf",
74        build: || {
75            // Single K_{2,2} biclique at rank 1 — matches the forward example.
76            let source = BicliqueCover::new(
77                BipartiteGraph::new(2, 2, vec![(0, 0), (0, 1), (1, 0), (1, 1)]),
78                1,
79            );
80            crate::example_db::specs::rule_example_with_witness::<_, BMF>(
81                source,
82                SolutionPair {
83                    // BicliqueCover (vertex-major, k=1): all 4 vertices in biclique 0
84                    source_config: vec![1, 1, 1, 1],
85                    // BMF (B row-major then C row-major): B=[[1],[1]], C=[[1,1]]
86                    target_config: vec![1, 1, 1, 1],
87                },
88            )
89        },
90    }]
91}
92
93#[cfg(test)]
94#[path = "../unit_tests/rules/bicliquecover_bmf.rs"]
95mod tests;
problemreductions/rules/bicliquecover_bmf.rs

problemreductions/rules/
bicliquecover_bmf.rs
