problemreductions/models/graph/
balanced_complete_bipartite_subgraph.rs

1use crate::registry::{FieldInfo, 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        module_path: module_path!(),
14        description: "Decide whether a bipartite graph contains a K_{k,k} subgraph",
15        fields: &[
16            FieldInfo { name: "graph", type_name: "BipartiteGraph", description: "The bipartite graph G = (A, B, E)" },
17            FieldInfo { name: "k", type_name: "usize", description: "Balanced biclique size" },
18        ],
19    }
20}
21
22#[derive(Debug, Clone, Serialize, Deserialize)]
23#[serde(from = "BalancedCompleteBipartiteSubgraphRepr")]
24pub struct BalancedCompleteBipartiteSubgraph {
25    graph: BipartiteGraph,
26    k: usize,
27    #[serde(skip)]
28    edge_lookup: HashSet<(usize, usize)>,
29}
30
31impl BalancedCompleteBipartiteSubgraph {
32    pub fn new(graph: BipartiteGraph, k: usize) -> Self {
33        let edge_lookup = Self::build_edge_lookup(&graph);
34        Self {
35            graph,
36            k,
37            edge_lookup,
38        }
39    }
40
41    pub fn graph(&self) -> &BipartiteGraph {
42        &self.graph
43    }
44
45    pub fn left_size(&self) -> usize {
46        self.graph.left_size()
47    }
48
49    pub fn right_size(&self) -> usize {
50        self.graph.right_size()
51    }
52
53    pub fn num_vertices(&self) -> usize {
54        self.left_size() + self.right_size()
55    }
56
57    pub fn num_edges(&self) -> usize {
58        self.graph.left_edges().len()
59    }
60
61    pub fn k(&self) -> usize {
62        self.k
63    }
64
65    fn build_edge_lookup(graph: &BipartiteGraph) -> HashSet<(usize, usize)> {
66        graph.left_edges().iter().copied().collect()
67    }
68
69    fn selected_vertices(&self, config: &[usize]) -> Option<(Vec<usize>, Vec<usize>)> {
70        if config.len() != self.num_vertices() {
71            return None;
72        }
73
74        let mut selected_left = Vec::new();
75        let mut selected_right = Vec::new();
76
77        for (index, &value) in config.iter().enumerate() {
78            match value {
79                0 => {}
80                1 => {
81                    if index < self.left_size() {
82                        selected_left.push(index);
83                    } else {
84                        selected_right.push(index - self.left_size());
85                    }
86                }
87                _ => return None,
88            }
89        }
90
91        Some((selected_left, selected_right))
92    }
93
94    fn has_selected_edge(&self, left: usize, right: usize) -> bool {
95        self.edge_lookup.contains(&(left, right))
96    }
97
98    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
99        self.evaluate(config).0
100    }
101}
102
103impl Problem for BalancedCompleteBipartiteSubgraph {
104    const NAME: &'static str = "BalancedCompleteBipartiteSubgraph";
105    type Value = crate::types::Or;
106
107    fn dims(&self) -> Vec<usize> {
108        vec![2; self.num_vertices()]
109    }
110
111    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
112        crate::types::Or({
113            let Some((selected_left, selected_right)) = self.selected_vertices(config) else {
114                return crate::types::Or(false);
115            };
116
117            if selected_left.len() != self.k || selected_right.len() != self.k {
118                return crate::types::Or(false);
119            }
120
121            selected_left.iter().all(|&left| {
122                selected_right
123                    .iter()
124                    .all(|&right| self.has_selected_edge(left, right))
125            })
126        })
127    }
128
129    fn variant() -> Vec<(&'static str, &'static str)> {
130        crate::variant_params![]
131    }
132}
133
134#[derive(Deserialize)]
135struct BalancedCompleteBipartiteSubgraphRepr {
136    graph: BipartiteGraph,
137    k: usize,
138}
139
140impl From<BalancedCompleteBipartiteSubgraphRepr> for BalancedCompleteBipartiteSubgraph {
141    fn from(repr: BalancedCompleteBipartiteSubgraphRepr) -> Self {
142        Self::new(repr.graph, repr.k)
143    }
144}
145
146crate::declare_variants! {
147    default BalancedCompleteBipartiteSubgraph => "1.3803^num_vertices",
148}
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
152    vec![crate::example_db::specs::ModelExampleSpec {
153        id: "balanced_complete_bipartite_subgraph",
154        instance: Box::new(BalancedCompleteBipartiteSubgraph::new(
155            BipartiteGraph::new(
156                4,
157                4,
158                vec![
159                    (0, 0),
160                    (0, 1),
161                    (0, 2),
162                    (1, 0),
163                    (1, 1),
164                    (1, 2),
165                    (2, 0),
166                    (2, 1),
167                    (2, 2),
168                    (3, 0),
169                    (3, 1),
170                    (3, 3),
171                ],
172            ),
173            3,
174        )),
175        optimal_config: vec![1, 1, 1, 0, 1, 1, 1, 0],
176        optimal_value: serde_json::json!(true),
177    }]
178}
179
180#[cfg(test)]
181#[path = "../../unit_tests/models/graph/balanced_complete_bipartite_subgraph.rs"]
182mod tests;
problemreductions/models/graph/balanced_complete_bipartite_subgraph.rs

problemreductions/models/graph/
balanced_complete_bipartite_subgraph.rs
