problemreductions/models/graph/

biclique_cover.rs

//! Biclique Cover problem implementation.
//!
//! Given a bipartite graph `G = (L ∪ R, E)` and a bound `k`, find up to `k`
//! bicliques whose union covers every edge of `G`. Each biclique must be a
//! *complete bipartite subgraph of `G`* — if `L_b ⊆ L` and `R_b ⊆ R` describe
//! biclique `b`, every pair `(l, r) ∈ L_b × R_b` must itself be an edge of `G`.
//! A biclique is *not* simply any pair `(L_b, R_b)`; the subgraph it induces
//! has to be complete. The objective minimizes the total number of vertex
//! memberships across all bicliques.
//!
//! Under this classical definition, the minimum `k` for which a rank-`k`
//! biclique cover exists is exactly the _Boolean rank_ of the biadjacency
//! matrix of `G` (Monson, Pullman, Rees 1995), matching exact Boolean
//! Matrix Factorization.

use crate::registry::{CreateSpec, ProblemSchemaEntry};
use crate::topology::BipartiteGraph;
use crate::traits::Problem;
use crate::types::Min;
use serde::{Deserialize, Serialize};
use std::collections::HashSet;

inventory::submit! {
    ProblemSchemaEntry {
        name: "BicliqueCover",
        display_name: "Biclique Cover",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Cover bipartite edges with k bicliques",
        fields: BicliqueCoverCreateSpec::FIELDS,
    }
}

/// The Biclique Cover problem.
///
/// Given a bipartite graph with vertex sets L and R, find k bicliques
/// that together cover all edges. Each vertex can be in any subset of the k bicliques.
///
/// # Example
///
/// ```
/// use problemreductions::models::graph::BicliqueCover;
/// use problemreductions::topology::BipartiteGraph;
/// use problemreductions::{Problem, BruteForce};
///
/// // Bipartite graph: L = {0, 1}, R = {0, 1}
/// // Edges: (0,0), (0,1), (1,0) in bipartite-local coordinates
/// let graph = BipartiteGraph::new(2, 2, vec![(0, 0), (0, 1), (1, 0)]);
/// let problem = BicliqueCover::new(graph, 2);
///
/// let solver = BruteForce::new();
/// let solutions = solver.find_all_witnesses(&problem).unwrap();
///
/// // Check coverage
/// for sol in &solutions {
///     assert!(problem.is_valid_cover(sol));
/// }
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct BicliqueCover {
    /// The bipartite graph.
    graph: BipartiteGraph,
    /// Number of bicliques to use.
    k: usize,
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct BicliqueCoverCreateSpec {
    /// Number of vertices in the left partition.
    left: usize,
    /// Number of vertices in the right partition.
    right: usize,
    /// Bipartite edges in left-local, right-local coordinates.
    #[create(codec = "bipartite-edge-list")]
    biedges: Vec<(usize, usize)>,
    /// Number of bicliques available to cover the edges.
    k: usize,
}

impl TryFrom<BicliqueCoverCreateSpec> for BicliqueCover {
    type Error = crate::registry::ConstructionError;

    fn try_from(spec: BicliqueCoverCreateSpec) -> Result<Self, Self::Error> {
        for (edge_index, &(left_vertex, right_vertex)) in spec.biedges.iter().enumerate() {
            if left_vertex >= spec.left {
                return Err(format!(
                    "biedges[{edge_index}] left vertex {left_vertex} is out of bounds for left partition size {}",
                    spec.left
                ).into());
            }
            if right_vertex >= spec.right {
                return Err(format!(
                    "biedges[{edge_index}] right vertex {right_vertex} is out of bounds for right partition size {}",
                    spec.right
                ).into());
            }
        }

        let graph = BipartiteGraph::new(spec.left, spec.right, spec.biedges);
        Ok(Self::new(graph, spec.k))
    }
}

impl BicliqueCover {
    /// Create a new Biclique Cover problem.
    ///
    /// # Arguments
    /// * `graph` - The bipartite graph
    /// * `k` - Number of bicliques
    pub fn new(graph: BipartiteGraph, k: usize) -> Self {
        Self { graph, k }
    }

    /// Create from a bipartite adjacency matrix.
    ///
    /// `Matrix[i][j] = 1` means edge between left vertex i and right vertex j.
    pub fn from_matrix(matrix: &[Vec<u8>], k: usize) -> Self {
        let left_size = matrix.len();
        let right_size = if left_size > 0 { matrix[0].len() } else { 0 };

        let mut edges = Vec::new();
        for (i, row) in matrix.iter().enumerate() {
            for (j, &val) in row.iter().enumerate() {
                if val != 0 {
                    edges.push((i, j));
                }
            }
        }

        Self {
            graph: BipartiteGraph::new(left_size, right_size, edges),
            k,
        }
    }

    /// Get the bipartite graph.
    pub fn graph(&self) -> &BipartiteGraph {
        &self.graph
    }

    /// Get the left partition size.
    pub fn left_size(&self) -> usize {
        self.graph.left_size()
    }

    /// Get the right partition size.
    pub fn right_size(&self) -> usize {
        self.graph.right_size()
    }

    /// Get the number of vertices.
    pub fn num_vertices(&self) -> usize {
        self.graph.left_size() + self.graph.right_size()
    }

    /// Get the number of edges.
    pub fn num_edges(&self) -> usize {
        self.graph.left_edges().len()
    }

    /// Get k (number of bicliques).
    pub fn k(&self) -> usize {
        self.k
    }

    /// Get the rank (alias for `k()`).
    pub fn rank(&self) -> usize {
        self.k()
    }

    /// Convert a configuration to biclique memberships.
    ///
    /// Each row gives one vertex's membership in the `k` bicliques.
    /// Returns: (left_memberships, right_memberships) where each is a Vec of k HashSets.
    fn get_biclique_memberships(
        &self,
        config: &[Vec<bool>],
    ) -> (Vec<HashSet<usize>>, Vec<HashSet<usize>>) {
        let n = self.num_vertices();
        let left_size = self.graph.left_size();
        let mut left_bicliques: Vec<HashSet<usize>> = vec![HashSet::new(); self.k];
        let mut right_bicliques: Vec<HashSet<usize>> = vec![HashSet::new(); self.k];

        for v in 0..n {
            for b in 0..self.k {
                if config
                    .get(b)
                    .and_then(|memberships| memberships.get(v))
                    .copied()
                    .unwrap_or(false)
                {
                    if v < left_size {
                        left_bicliques[b].insert(v);
                    } else {
                        right_bicliques[b].insert(v);
                    }
                }
            }
        }

        (left_bicliques, right_bicliques)
    }

    /// Check if an edge is covered by the bicliques.
    ///
    /// Takes edge endpoints in unified vertex space.
    fn is_edge_covered(&self, left: usize, right: usize, config: &[Vec<bool>]) -> bool {
        let (left_bicliques, right_bicliques) = self.get_biclique_memberships(config);

        // Edge is covered if both endpoints are in the same biclique
        for b in 0..self.k {
            if left_bicliques[b].contains(&left) && right_bicliques[b].contains(&right) {
                return true;
            }
        }
        false
    }

    /// Check if a configuration is a valid biclique cover.
    pub fn is_valid_solution(&self, config: &[Vec<bool>]) -> bool {
        self.is_valid_cover(config)
    }

    /// Check if the configuration is a valid biclique cover.
    ///
    /// Under the classical definition, a biclique is a complete bipartite
    /// subgraph of the input graph: every pair `(l, r)` with `l ∈ L_b`
    /// and `r ∈ R_b` must be an edge of `G`. A configuration is a valid
    /// biclique cover iff every biclique is a sub-biclique of `G` and
    /// every edge of `G` is covered by at least one biclique.
    pub fn is_valid_cover(&self, config: &[Vec<bool>]) -> bool {
        use crate::topology::Graph;
        let (left_bicliques, right_bicliques) = self.get_biclique_memberships(config);
        let left_size = self.graph.left_size();
        // Every biclique must be a sub-biclique of G (no non-edges covered).
        for b in 0..self.k {
            for &l in &left_bicliques[b] {
                for &r in &right_bicliques[b] {
                    // Endpoints come from get_biclique_memberships in unified
                    // vertex space: l < left_size, r >= left_size.
                    debug_assert!(l < left_size && r >= left_size);
                    if !self.graph.has_edge(l, r) {
                        return false;
                    }
                }
            }
        }
        // Every edge of G must be covered by at least one biclique.
        self.graph
            .edges()
            .iter()
            .all(|&(l, r)| self.is_edge_covered(l, r, config))
    }

    /// Count covered edges.
    pub fn count_covered_edges(
        &self,
        config: &[Vec<bool>],
    ) -> Result<i64, crate::traits::EvaluationError> {
        use crate::topology::Graph;
        let count = self
            .graph
            .edges()
            .iter()
            .filter(|&&(l, r)| self.is_edge_covered(l, r, config))
            .count();
        i64::try_from(count).map_err(|_| {
            crate::traits::EvaluationError::IntegerOverflow(
                "converting covered-edge count to i64".into(),
            )
        })
    }

    /// Count total biclique size (sum of vertices in all bicliques).
    pub fn total_biclique_size(
        &self,
        config: &[Vec<bool>],
    ) -> Result<i64, crate::traits::EvaluationError> {
        let size = config
            .iter()
            .flatten()
            .filter(|&&selected| selected)
            .count();
        i64::try_from(size).map_err(|_| {
            crate::traits::EvaluationError::IntegerOverflow(
                "converting total biclique size to i64".into(),
            )
        })
    }
}

/// Check if a biclique configuration covers all edges.
#[cfg(test)]
pub(crate) fn is_biclique_cover(
    edges: &[(usize, usize)],
    left_bicliques: &[HashSet<usize>],
    right_bicliques: &[HashSet<usize>],
) -> bool {
    let edge_set: HashSet<(usize, usize)> = edges
        .iter()
        .map(|&(u, v)| if u <= v { (u, v) } else { (v, u) })
        .collect();

    let all_bicliques_are_subgraphs =
        left_bicliques
            .iter()
            .zip(right_bicliques.iter())
            .all(|(lb, rb)| {
                lb.iter().all(|&l| {
                    rb.iter().all(|&r| {
                        let edge = if l <= r { (l, r) } else { (r, l) };
                        edge_set.contains(&edge)
                    })
                })
            });

    all_bicliques_are_subgraphs
        && edges.iter().all(|&(l, r)| {
            left_bicliques
                .iter()
                .zip(right_bicliques.iter())
                .any(|(lb, rb)| lb.contains(&l) && rb.contains(&r))
        })
}

impl Problem for BicliqueCover {
    const NAME: &'static str = "BicliqueCover";
    type Solution = Vec<Vec<bool>>;
    type Value = Min<i64>;

    crate::problem_parameters![
        ("left_size", left_size),
        ("num_edges", num_edges),
        ("num_vertices", num_vertices),
        ("rank", rank),
        ("right_size", right_size),
    ];

    fn evaluate(
        &self,
        solution: &Self::Solution,
    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
        if solution.len() != self.k
            || solution
                .iter()
                .any(|biclique| biclique.len() != self.num_vertices())
        {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "biclique membership dimensions do not match the instance".into(),
            ));
        }
        Ok({
            if !self.is_valid_cover(solution) {
                return Ok(Min(None));
            }
            Min(Some(self.total_biclique_size(solution)?))
        })
    }

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }
}

impl crate::solvers::BruteForceProblem for BicliqueCover {
    fn dimensions(&self) -> Vec<usize> {
        // Each vertex has k binary variables (one per biclique)
        vec![2; self.num_vertices() * self.k]
    }
}

crate::declare_variants! {
    default BicliqueCover => "2^(num_vertices * rank)" create BicliqueCoverCreateSpec,
}

crate::register_brute_force! {
    BicliqueCover decode |problem: &BicliqueCover, indices: Vec<usize>| (0..problem.rank()).map(|biclique| (0..problem.num_vertices()).map(|vertex| indices[vertex * problem.rank() + biclique] != 0).collect()).collect(),
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    use crate::topology::BipartiteGraph;
    // Biclique 0: L_0={ℓ_1}, R_0={r_1, r_2} — covers edges (0,0), (0,1).
    // Biclique 1: L_1={ℓ_2}, R_1={r_2, r_3} — covers edges (1,1), (1,2).
    // Both are sub-bicliques of G; every edge covered; total size = 6.
    // One incidence row per biclique over the five vertices.
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "biclique_cover",
        instance: Box::new(BicliqueCover::new(
            BipartiteGraph::new(2, 3, vec![(0, 0), (0, 1), (1, 1), (1, 2)]),
            2,
        )),
        optimal_config: serde_json::json!(vec![
            vec![true, false, true, true, false],
            vec![false, true, false, true, true]
        ]),
        optimal_value: serde_json::json!(6),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/graph/biclique_cover.rs"]
mod tests;