problemreductions/models/graph/
balanced_complete_bipartite_subgraph.rs

1use crate::registry::{CreateSpec, ProblemSchemaEntry};
2use crate::topology::BipartiteGraph;
3use crate::traits::Problem;
4use serde::{Deserialize, Serialize};
5use std::collections::HashSet;
6
7inventory::submit! {
8    ProblemSchemaEntry {
9        name: "BalancedCompleteBipartiteSubgraph",
10        display_name: "Balanced Complete Bipartite Subgraph",
11        aliases: &[],
12        dimensions: &[],
13        category: crate::registry::ProblemCategory::Graph,
14        module_path: module_path!(),
15        description: "Decide whether a bipartite graph contains a K_{k,k} subgraph",
16        fields: BalancedCompleteBipartiteSubgraphCreateSpec::FIELDS,
17    }
18}
19
20#[derive(Debug, Clone, Serialize, Deserialize)]
21#[serde(from = "BalancedCompleteBipartiteSubgraphRepr")]
22pub struct BalancedCompleteBipartiteSubgraph {
23    graph: BipartiteGraph,
24    k: usize,
25    #[serde(skip)]
26    edge_lookup: HashSet<(usize, usize)>,
27}
28
29#[derive(Debug, Deserialize, crate::CreateSpec)]
30struct BalancedCompleteBipartiteSubgraphCreateSpec {
31    /// Number of vertices in the left partition.
32    left: usize,
33    /// Number of vertices in the right partition.
34    right: usize,
35    /// Bipartite edges in left-local, right-local coordinates.
36    #[create(codec = "bipartite-edge-list")]
37    biedges: Vec<(usize, usize)>,
38    /// Balanced biclique size.
39    k: usize,
40}
41
42impl TryFrom<BalancedCompleteBipartiteSubgraphCreateSpec> for BalancedCompleteBipartiteSubgraph {
43    type Error = crate::registry::ConstructionError;
44
45    fn try_from(spec: BalancedCompleteBipartiteSubgraphCreateSpec) -> Result<Self, Self::Error> {
46        for (index, &(left, right)) in spec.biedges.iter().enumerate() {
47            if left >= spec.left {
48                return Err(format!(
49                    "biedges[{index}] left vertex {left} is out of bounds for left partition size {}",
50                    spec.left
51                ).into());
52            }
53            if right >= spec.right {
54                return Err(format!(
55                    "biedges[{index}] right vertex {right} is out of bounds for right partition size {}",
56                    spec.right
57                ).into());
58            }
59        }
60        Ok(Self::new(
61            BipartiteGraph::new(spec.left, spec.right, spec.biedges),
62            spec.k,
63        ))
64    }
65}
66
67impl BalancedCompleteBipartiteSubgraph {
68    pub fn new(graph: BipartiteGraph, k: usize) -> Self {
69        let edge_lookup = Self::build_edge_lookup(&graph);
70        Self {
71            graph,
72            k,
73            edge_lookup,
74        }
75    }
76
77    pub fn graph(&self) -> &BipartiteGraph {
78        &self.graph
79    }
80
81    pub fn left_size(&self) -> usize {
82        self.graph.left_size()
83    }
84
85    pub fn right_size(&self) -> usize {
86        self.graph.right_size()
87    }
88
89    pub fn num_vertices(&self) -> usize {
90        self.left_size() + self.right_size()
91    }
92
93    pub fn num_edges(&self) -> usize {
94        self.graph.left_edges().len()
95    }
96
97    pub fn k(&self) -> usize {
98        self.k
99    }
100
101    fn build_edge_lookup(graph: &BipartiteGraph) -> HashSet<(usize, usize)> {
102        graph.left_edges().iter().copied().collect()
103    }
104
105    fn selected_vertices(&self, config: &[bool]) -> Option<(Vec<usize>, Vec<usize>)> {
106        if config.len() != self.num_vertices() {
107            return None;
108        }
109
110        let mut selected_left = Vec::new();
111        let mut selected_right = Vec::new();
112
113        for (index, &selected) in config.iter().enumerate() {
114            if selected {
115                if index < self.left_size() {
116                    selected_left.push(index);
117                } else {
118                    selected_right.push(index - self.left_size());
119                }
120            }
121        }
122
123        Some((selected_left, selected_right))
124    }
125
126    fn has_selected_edge(&self, left: usize, right: usize) -> bool {
127        self.edge_lookup.contains(&(left, right))
128    }
129
130    pub fn is_valid_solution(
131        &self,
132        config: &[bool],
133    ) -> Result<bool, crate::traits::EvaluationError> {
134        if config.len() != self.num_vertices() {
135            return Err(crate::traits::EvaluationError::InvalidConfiguration(
136                "vertex-selection length does not match the graph".into(),
137            ));
138        }
139        let Some((selected_left, selected_right)) = self.selected_vertices(config) else {
140            return Ok(false);
141        };
142
143        if selected_left.len() != self.k || selected_right.len() != self.k {
144            return Ok(false);
145        }
146
147        Ok(selected_left.iter().all(|&left| {
148            selected_right
149                .iter()
150                .all(|&right| self.has_selected_edge(left, right))
151        }))
152    }
153}
154
155impl Problem for BalancedCompleteBipartiteSubgraph {
156    const NAME: &'static str = "BalancedCompleteBipartiteSubgraph";
157    type Solution = Vec<bool>;
158    type Value = crate::types::Or;
159
160    crate::problem_parameters![
161        ("k", k),
162        ("left_size", left_size),
163        ("num_vertices", num_vertices),
164        ("right_size", right_size),
165    ];
166
167    fn evaluate(
168        &self,
169        config: &Self::Solution,
170    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
171        Ok(crate::types::Or(self.is_valid_solution(config)?))
172    }
173
174    fn variant() -> Vec<(&'static str, &'static str)> {
175        crate::variant_params![]
176    }
177}
178
179impl crate::solvers::BruteForceProblem for BalancedCompleteBipartiteSubgraph {
180    fn dimensions(&self) -> Vec<usize> {
181        vec![2; self.num_vertices()]
182    }
183}
184
185#[derive(Deserialize)]
186struct BalancedCompleteBipartiteSubgraphRepr {
187    graph: BipartiteGraph,
188    k: usize,
189}
190
191impl From<BalancedCompleteBipartiteSubgraphRepr> for BalancedCompleteBipartiteSubgraph {
192    fn from(repr: BalancedCompleteBipartiteSubgraphRepr) -> Self {
193        Self::new(repr.graph, repr.k)
194    }
195}
196
197crate::declare_variants! {
198    default BalancedCompleteBipartiteSubgraph => "1.3803^num_vertices" create BalancedCompleteBipartiteSubgraphCreateSpec,
199}
200
201crate::register_brute_force! {
202    BalancedCompleteBipartiteSubgraph decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
203}
204
205#[cfg(feature = "example-db")]
206pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
207    vec![crate::example_db::specs::ModelExampleSpec {
208        id: "balanced_complete_bipartite_subgraph",
209        instance: Box::new(BalancedCompleteBipartiteSubgraph::new(
210            BipartiteGraph::new(
211                4,
212                4,
213                vec![
214                    (0, 0),
215                    (0, 1),
216                    (0, 2),
217                    (1, 0),
218                    (1, 1),
219                    (1, 2),
220                    (2, 0),
221                    (2, 1),
222                    (2, 2),
223                    (3, 0),
224                    (3, 1),
225                    (3, 3),
226                ],
227            ),
228            3,
229        )),
230        optimal_config: serde_json::json!(vec![true, true, true, false, true, true, true, false]),
231        optimal_value: serde_json::json!(true),
232    }]
233}
234
235#[cfg(test)]
236#[path = "../../unit_tests/models/graph/balanced_complete_bipartite_subgraph.rs"]
237mod tests;
problemreductions/models/graph/balanced_complete_bipartite_subgraph.rs

problemreductions/models/graph/
balanced_complete_bipartite_subgraph.rs
