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(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        Ok(config_bmf_to_bc(target_solution, self.m, self.n, self.k))
46    }
47}
48
49#[reduction(
50    transform = exact {
51        rows = "left_size",
52        cols = "right_size",
53        rank = "rank",
54    }
55)]
56impl ReduceTo<BMF> for BicliqueCover {
57    type Result = ReductionBicliqueCoverToBMF;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let m = self.left_size();
61        let n = self.right_size();
62        let k = self.k();
63        let mut matrix = vec![vec![false; n]; m];
64        for &(i, j) in self.graph().left_edges() {
65            matrix[i][j] = true;
66        }
67        let target = BMF::new(matrix, k);
68        Ok(ReductionBicliqueCoverToBMF { target, m, n, k })
69    }
70}
71
72#[cfg(feature = "example-db")]
73pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
74    use crate::export::SolutionPair;
75    use crate::topology::BipartiteGraph;
76
77    vec![crate::example_db::specs::RuleExampleSpec {
78        id: "bicliquecover_to_bmf",
79        build: || {
80            // Single K_{2,2} biclique at rank 1 — matches the forward example.
81            let source = BicliqueCover::new(
82                BipartiteGraph::new(2, 2, vec![(0, 0), (0, 1), (1, 0), (1, 1)]),
83                1,
84            );
85            crate::example_db::specs::rule_example_with_witness::<_, BMF>(
86                source,
87                SolutionPair {
88                    source_config: serde_json::json!(vec![vec![true, true, true, true]]),
89                    target_config: serde_json::json!((
90                        vec![vec![true], vec![true]],
91                        vec![vec![true, true]]
92                    )),
93                },
94            )
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/bicliquecover_bmf.rs"]
101mod tests;
problemreductions/rules/bicliquecover_bmf.rs

problemreductions/rules/
bicliquecover_bmf.rs
